Źródło: Arkusze CKE
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
Warianty odpowiedzi
-
A
O(n log n)
-
B
O(n2)
-
C
O(n)
-
D
O(1)
Wyjaśnienie
Przeanalizujmy krok po kroku działanie tego kodu, aby określić jego złożoność obliczeniową.
Algorytm rozpoczyna pracę od pierwszego elementu (indeks 0) i przesuwa się krok po kroku do przodu o 1, dopóki nie przejdzie przez wszystkie elementy n-elementowej tablicy.
W najgorszym scenariuszu – gdy szukany element x znajduje się na samym końcu lub nie ma go wcale – pętla wykona się dokładnie n razy.
Skoro liczba wykonanych kroków rośnie wprost proporcjonalnie do liczby danych wejściowych n, mamy do czynienia z liniową złożonością obliczeniową, zdefiniowaną jako O(n).