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