Pytanie 1
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
A. O(1)
B. O(n log n)
C. O(n)
D. O(n2)
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.
