Jaką złożoność obliczeniową posiada podany algorytm?
Dane:
Tablica: tab[n]
Index: i = 0, 1, ..., n-1
x: szukana
Algorytm:
// K1: i ← 0
// K2: dopóki i < (n - 1)
// K3: jeżeli tab[i] = x to wypisz i
// K4: i ← i + 1
// K5: idź do K2
// K6: zakończ
Analizując podany algorytm, warto zauważyć, że przechodzi on przez każdy element tablicy dokładnie raz, zaczynając od indeksu 0 aż do n-1. To jest klasyczny przykład przeszukiwania liniowego (linear search), które w najgorszym przypadku ma złożoność czasową O(n), gdzie n to liczba elementów w tablicy. Moim zdaniem to jedna z najbardziej podstawowych i jednocześnie często używanych technik, szczególnie tam, gdzie dane nie są posortowane albo kiedy oczekujemy prostoty implementacji. W praktyce taki algorytm stosuje się, gdy nie zależy nam na super efektywności, a raczej na łatwości zrozumienia kodu lub szybkim prototypowaniu, na przykład podczas pisania skryptów narzędziowych lub prostych aplikacji. Branżowe standardy, chociażby w programowaniu niskopoziomowym lub w zastosowaniach embedded, też często bazują na tego typu rozwiązaniach, ponieważ nie wymagają one dodatkowej pamięci ani zaawansowanych struktur danych. Fajnie zwrócić uwagę, że O(n) oznacza, iż czas wykonywania rośnie proporcjonalnie do liczby elementów – czyli dla 1 000 elementów algorytm wykona się około 1 000 razy wolniej niż dla pojedynczego elementu, chociaż w praktyce zależy to oczywiście od wielu czynników sprzętowych. Dobrym zwyczajem jest zawsze na początku próbować rozwiązać problem najprostszym algorytmem, takim jak ten, a dopiero potem – jeśli wydajność zawiedzie – szukać bardziej zaawansowanych rozwiązań, jak wyszukiwanie binarne czy struktury indeksujące.
W kontekście złożoności obliczeniowej łatwo wpaść w pułapkę myślenia, że algorytm wydaje się bardziej złożony, niż jest w rzeczywistości. Przykładowo, wybór O(n log n) sugeruje obecność jakiegoś sortowania lub podziału danych, co zupełnie nie występuje w tym rozwiązaniu – tu nie ma rekurencji, dzielenia na podtablice ani żadnych bardziej skomplikowanych operacji. Złożoność O(n^2) typowa jest dla algorytmów, gdzie mamy zagnieżdżone pętle, czyli każda iteracja głównej pętli wyzwala kolejną pełną pętlę po danych – a tutaj pętla jest tylko jedna i przechodzi przez tablicę jeden raz. Bardzo często myli się to z sortowaniem bąbelkowym czy selekcyjnym, gdzie rzeczywiście występuje kwadratowa złożoność, ale nie w prostym przeszukiwaniu liniowym. Z kolei O(1), czyli czas stały, dotyczy tylko takich algorytmów, gdzie liczba operacji nie zależy od wielkości wejścia – na przykład odczytanie elementu z tablicy po znanym indeksie. Tu jednak liczba kroków wzrasta liniowo wraz z n, czyli liczbą elementów, więc niestety nie jest to czas stały. Moim zdaniem, wiele osób błędnie utożsamia prostotę kodu z czasem stałym, ale w rzeczywistości chodzi o to, jak algorytm zachowuje się, gdy ilość danych znacząco rośnie. W tej sytuacji odpowiednia analiza pętli i sposobu przetwarzania danych pozwala szybko zauważyć, że algorytm ten to klasyczne O(n), zgodne z najprostszymi wzorcami algorytmicznymi spotykanymi w praktyce.