programowanie asembler algorytmy

pojęcia i definicje

Studiując poszczególne algorytmy należy zapoznać się z kilkoma pojęciami:

Złożoność

Jest to zależność czasu wykonania do wielkości zbioru danych do posortowania. Zapisuje się ją symbolem O (notacja dużego O). W zapisie złożoności nie uwzględnia się żadnych stałych - tzn. złożoność O(n) jest równa złożoności O(2n). Tak więc dwa algorytmy mające taką samą złożoność mogą mieć różne czasy wykonania. Na marginesie dodam, że notacja dużego O nie odnosi się tylko do czasu wykonania, ale także np. do zajętości pamięci. Oto przykłady złożoności:

O(n pow 2) złożoność kwadratowa, tzn. gdy rozmiar danych wzrasta dwukrotnie to czas wykonania wzrasta czterokrotnie
O(n) złożoność liniowa, tzn. czas wykonania jest wprost proporcjonalny do rozmiaru danych
O(1) złożoność stała, tzn. czas wykonania jest taki sam bez względu na rozmiar danych
O(log n) złożoność logarytmiczna
O(n log n) złożoność liniowologarytmiczna
O(sqrt n) złożoność pierwiastkowa

Dodam jeszcze, że złożoność algorytmów może zmieniać się w zależności od danych wejściowych. Tak więc algorytm o średniej złożoności O(n log n) może dla pewnych danych degradować się do poziomu O(n pow 2) (np: quicksort) lub algorytm o średnim czasie wykonania O(n pow 2) może dla pewnych danych osiągać złożoność O(n) (np: insertionsort).