ID: 2755
Algorytmy
Łatwe
Źródło: Arkusze CKE
Jaka będzie złożoność czasowa wyszukiwania w posortowanej tablicy przy użyciu algorytmu binarnego?
Warianty odpowiedzi
-
A
O(n log n)
-
B
O(n)
-
C
O(log n)
-
D
O(n²)
Wyjaśnienie
Kluczem do zrozumienia wydajności wyszukiwania binarnego jest fakt, że w każdym krok odrzucamy dokładnie połowę pozostałych elementów.
Jeśli masz tablicę z milionem rekordów, po pierwszym kroku zostaje pół miliona, po drugim 250 tysięcy i tak dalej.
Liczba kroków potrzebna do znalezienia elementu rośnie niezwykle wolno i opisuje ją funkcja logarytmiczna.
Stąd złożoność czasowa wynosi O(log n), co oznacza błyskawiczne działanie nawet przy ogromnych zbiorach danych.