jak obliczyć złożoność wyszukiwania binarnego


144

Słyszałem, jak ktoś powiedział, że skoro wyszukiwanie binarne zmniejsza o połowę dane wejściowe wymagane do wyszukiwania, jest to algorytm log (n). Ponieważ nie jestem z wykształcenia matematycznego, nie mogę się do tego odnieść. Czy ktoś może to wyjaśnić bardziej szczegółowo? czy to ma coś wspólnego z szeregiem logarytmicznym?


Odpowiedzi:


385

Tutaj bardziej matematyczny sposób patrzenia na to, choć niezbyt skomplikowany. IMO dużo jaśniejsze niż te nieformalne:

Pytanie brzmi, ile razy możesz podzielić N przez 2, aż będziesz miał 1? Zasadniczo oznacza to, że wykonaj wyszukiwanie binarne (połowa elementów), dopóki go nie znajdziesz. W formule wyglądałoby to tak:

1 = N / 2 x

pomnóż przez 2 x :

2 x = N

teraz zrób dziennik 2 :

log 2 (2 x ) = log 2 N
x * log 2 (2) = log 2 N
x * 1 = log 2 N

oznacza to, że możesz podzielić log N razy, aż wszystko zostanie podzielone. Co oznacza, że ​​musisz dzielić log N („wykonaj krok wyszukiwania binarnego”), aż znajdziesz element.


właśnie obliczyłem to do t (n) = (2 ^ 2) * K. jak zrobić to do logowania formularz?
Shan Khan

1
ta sama koncepcja wyjaśniona graficznie: stackoverflow.com/a/13093274/550393
2cupsOfTech

Brakuje mi części, jeśli masz BST z 7 wpisami, jaka jest jego formuła? log2 (7)? Wykonałem obliczenia brutalnej siły dla każdego możliwego wyniku i otrzymałem odpowiedź, która nie jest równa log2 (7), więc co robię źle?
Perry Monschau

1
O wiele łatwiejsze niż wyjaśnienie drzewa binarnego.
NoName

1
Bardzo dobra odpowiedź
VHS

22

W przypadku wyszukiwania binarnego, T (N) = T (N / 2) + O (1) // relacja powtarzania

Zastosuj twierdzenie Mastersa do obliczenia złożoności czasu wykonywania relacji rekurencyjnych: T (N) = aT (N / b) + f (N)

Tutaj a = 1, b = 2 => log (a base b) = 1

także tutaj f (N) = n ^ c log ^ k (n) // k = 0 & c = log (a base b)

Zatem T (N) = O (N ^ c log ^ (k + 1) N) = O (log (N))

Źródło: http://en.wikipedia.org/wiki/Master_theorem


1
dlaczego log (podstawa b) to 1, gdy a = 1 i b = 2, czy nie powinno to być 0?
GAURANG VYAS

16

T (n) = T (n / 2) +1

T (n / 2) = T (n / 4) + 1 + 1

Wpisz wartość The (n / 2) powyżej, aby T (n) = T (n / 4) + 1 + 1. . . . T (n / 2 ^ k) + 1 + 1 + 1 ..... + 1

= T (2 ^ k / 2 ^ k) + 1 + 1 .... + 1 aż do k

= T (1) + k

Ponieważ wzięliśmy 2 ^ k = n

K = log n

Więc złożoność czasowa wynosi O (log n)


10

Nie ma połowy czasu wyszukiwania, to nie spowodowałoby zarejestrowania (n). Zmniejsza ją logarytmicznie. Pomyśl o tym przez chwilę. Gdybyś miał 128 wpisów w tabeli i musiałbyś wyszukiwać liniowo pod kątem swojej wartości, prawdopodobnie znalezienie wartości zajęłoby średnio około 64 wpisów. To jest n / 2 lub czas liniowy. Przy wyszukiwaniu binarnym eliminujesz 1/2 możliwych wpisów w każdej iteracji, tak że znalezienie wartości wymagałoby najwyżej 7 porównań (podstawa logu 2 ze 128 to 7 lub 2 do potęgi 7 to 128). moc wyszukiwania binarnego.


Przepraszam za nekropostę, ale 128 nie jest równo wypełnionym drzewem. Użyłem prostego przykładu, aby to obejść, i odkryłem, że 7 wpisów równomiernie wypełnia drzewo 3 warstwami. Obliczyłem, że złożoność powinna wynosić 17/7 (średnia z sumy porównań), czyli 2,43. Ale log2 (7) to 2,81. Więc czego mi tu brakuje?
Perry Monschau

Dwie odpowiedzi - pierwsza tutaj: Nawet jeśli nie ma błędu w matematyce, widzimy, że średnia 2,43 jest nadal lepsza niż średnia 3,5 dla liniowej, a to jest niska wartość. Gdy dojdziesz do setek wpisów, log2 () jest znacznie lepsza niż linear. Myślę, że to widzisz, więc przejdźmy dalej.
Michael Dorgan

1
Druga odpowiedź: nie jestem pewien, jakie masz drzewo, gdzie 7 ma wszystko wypełnione. Kiedy myślę o idealnym drzewie z 8 wejściami, widzę drzewo o głębokości 3 poziomów z 8 liśćmi. W tym drzewie, bez względu na to, jaką liczbę przeszukujesz, przejście od korzenia do liścia zajmuje łącznie 3 porównania. W przypadku 7 wpisów jedna ze ścieżek zajmie jedno porównanie mniej, czyli 20/7 (6 węzłów po 3 porównania, 1 węzeł z 2 porównaniami), czyli ~ 2,85. Log2 (7) wynosi ~ 2,81. Nie mam podstaw matematycznych, aby wyjaśnić różnicę 0,04, ale wydaje mi się, że ma to związek z brakiem dostępnych bitów ułamkowych lub innej magii :)
Michael Dorgan

liczba to liczba liści !? Nie liczba węzłów? Cóż, to była duża informacja, której mi brakowało. Wydaje mi się dziwne, że funkcja jest oparta na liściach, kiedy każdy rozgałęziony węzeł jest również potencjalnym punktem zatrzymania. W każdym razie, dzięki za wyjaśnienie tego dla mnie!
Perry Monschau

5

Złożoność czasowa algorytmu wyszukiwania binarnego należy do klasy O (log n). To się nazywa asymptotyczne tempo wzrostu . Sposób, w jaki należy to interpretować, jest taki, że asymptotyczny wzrost czasu wykonywania funkcji przy danym zestawie wejściowym o rozmiarze n nie przekroczy log n.

To jest po prostu formalny żargon matematyczny, aby móc udowodnić twierdzenia itp. Ma bardzo proste wyjaśnienie. Gdy n rośnie bardzo duże, funkcja log n przekroczy czas potrzebny do wykonania funkcji. Rozmiar „zbioru wejściowego”, n, to tylko długość listy.

Mówiąc najprościej, powodem, dla którego wyszukiwanie binarne jest O (log n), jest to, że zmniejsza o połowę dane wejściowe ustawione w każdej iteracji. Łatwiej o tym pomyśleć w odwrotnej sytuacji. W przypadku x iteracji, jak długą listę może zbadać algorytm wyszukiwania binarnego przy max? Odpowiedź to 2 ^ x. Z tego widać, że odwrotność jest taka, że ​​średnio algorytm wyszukiwania binarnego potrzebuje log2 n iteracji dla listy o długości n.

Jeśli dlaczego jest O (log n), a nie O (log2 n), to dlatego, że po prostu wstaw ponownie - Używanie dużych stałych notacji O nie liczy się.


4

Oto wikipedia wpis w

Jeśli spojrzysz na proste podejście iteracyjne. Po prostu eliminujesz połowę elementów do wyszukania, aż znajdziesz element, którego potrzebujesz.

Oto wyjaśnienie, w jaki sposób tworzymy wzór.

Powiedzmy, że początkowo masz N elementów, a następnie przy pierwszej próbie zrobisz „N / 2”. Gdzie N jest sumą dolnej granicy i górnej granicy. Pierwsza wartość czasu N byłaby równa (L + H), gdzie L to pierwszy indeks (0), a H to ostatni indeks listy, której szukasz. Jeśli masz szczęście, element, który próbujesz znaleźć, będzie w środku [np. Szukasz 18 na liście {16, 17, 18, 19, 20}, a następnie obliczasz ⌊ (0 + 4) / 2⌋ = 2, gdzie 0 to dolna granica (L - indeks pierwszego elementu tablicy) a 4 to wyższa granica (H - indeks ostatniego elementu tablicy). W powyższym przypadku L = 0 i H = 4. Teraz 2 to indeks znalezionego elementu 18. Bingo! Znalazłeś to.

Gdyby przypadek był inną tablicą {15,16,17,18,19}, ale nadal szukałeś 18, nie miałbyś szczęścia i zrobiłbyś pierwsze N ​​/ 2 (czyli ⌊ (0 + 4) / 2⌋ = 2, a następnie zdaj sobie sprawę, że element 17 pod indeksem 2. nie jest liczbą, której szukasz. Teraz wiesz, że nie musisz szukać co najmniej połowy tablicy podczas następnej próby iteracyjnego wyszukiwania. wysiłek związany z wyszukiwaniem jest zmniejszony o połowę, więc zasadniczo nie przeszukujesz połowy listy elementów, które przeszukiwałeś wcześniej, za każdym razem, gdy próbujesz znaleźć element, którego nie mogłeś znaleźć w poprzedniej próbie.

Więc najgorszy byłby przypadek

[N] / 2 + [(N / 2)] / 2 + [((N / 2) / 2)] / 2 .....
tj .:
N / 2 1 + N / 2 2 + N / 2 3 + ..... + N / 2 x … ..

aż… zakończysz wyszukiwanie, gdzie w szukanym elemencie znajduje się na końcu listy.

To pokazuje, że w najgorszym przypadku osiągniesz N / 2 x, gdzie x jest takie, że 2 x = N

W innych przypadkach N / 2 x gdzie x jest takie, że 2 x <N Minimalna wartość x może wynosić 1, co jest najlepszym przypadkiem.

Ponieważ matematycznie najgorszym przypadkiem jest sytuacja, w której wartość
2 x = N
=> log 2 (2 x ) = log 2 (N)
=> x * log 2 (2) = log 2 (N)
=> x * 1 = log 2 (N)
=> Bardziej formalnie ⌊log 2 (N) + 1⌋


1
Jak dokładnie uzyskujesz bardziej formalną wersję?
Kalle,

Używana jest funkcja podłogi. Szczegóły znajdują się w sekcji wydajności linku wiki ( en.wikipedia.org/wiki/Binary_search_algorithm ) podanego w odpowiedzi.
RajKon


2

Powiedzmy, że iteracja w wyszukiwaniu binarnym kończy się po k iteracji. W każdej iteracji tablica jest dzielona na pół. Powiedzmy, że długość tablicy w dowolnej iteracji wynosi n. W iteracji 1,

Length of array = n

W iteracji 2,

Length of array = n⁄2

W iteracji 3,

Length of array = (n⁄2)⁄2 = n⁄22

Dlatego po iteracji k,

Length of array = n⁄2k

Wiemy również, że po k podziałach długość tablicy wynosi 1 Dlatego

Length of array = n⁄2k = 1
=> n = 2k

Stosowanie funkcji dziennika po obu stronach:

=> log2 (n) = log2 (2k)
=> log2 (n) = k log2 (2)
As (loga (a) = 1)

W związku z tym,

As (loga (a) = 1)
k = log2 (n)

Stąd złożoność czasowa wyszukiwania binarnego

log2 (n)

1

Wyszukiwanie binarne polega na wielokrotnym dzieleniu problemu na pół, mniej więcej tak (szczegóły pominięto):

Przykład szukania 3 w [4,1,3,8,5]

  1. Zamów listę elementów [1,3,4,5,8]
  2. Spójrz na środkową pozycję (4),
    • Jeśli tego szukasz, przestań
    • Jeśli jest większy, spójrz na pierwszą połowę
    • Jeśli jest mniej, spójrz na drugą połowę
  3. Powtórz krok 2 z nową listą [1, 3], znajdź 3 i zatrzymaj się

Jest to bi wyszukiwania -nary po podzieleniu problemu w 2.

Wyszukiwanie wymaga tylko kroków log2 (n), aby znaleźć poprawną wartość.

Poleciłbym wprowadzenie do algorytmów, jeśli chcesz poznać złożoność algorytmów.


1

Ponieważ za każdym razem skracamy listę o połowę, musimy tylko wiedzieć, z ilu kroków otrzymujemy 1, dzieląc listę przez dwa. W podanym niżej obliczeniu x oznacza liczbę czasu, przez jaki dzielimy listę, aż otrzymamy jeden element (w najgorszym przypadku).

1 = N / 2x

2x = N

Biorąc log2

log2 (2x) = log2 (N)

x * log2 (2) = log2 (N)

x = log2 (N)


1

T (N) = T (N / 2) + 1

T (N) = T (N / 2) + 1 = (T (N / 4) + 1) + 1

...

T (N) = T (N / N) + (1 + 1 + 1 + ... + 1) = 1 + logN (podstawa 2 log) = 1 + logN

Zatem złożoność czasowa wyszukiwania binarnego wynosi O (logN)


0
ok see this
for(i=0;i<n;n=n/2)
{
i++;
}
1. Suppose at i=k the loop terminate. i.e. the loop execute k times.

2. at each iteration n is divided by half.

2.a n=n/2                   .... AT I=1
2.b n=(n/2)/2=n/(2^2)
2.c n=((n/2)/2)/2=n/(2^3)....... aT I=3
2.d n=(((n/2)/2)/2)/2=n/(2^4)

So at i=k , n=1 which is obtain by dividing n  2^k times
n=2^k
1=n/2^k 
k=log(N)  //base 2

0

Ułatwię wam wszystkim na przykładzie.

Dla uproszczenia załóżmy, że tablica zawiera 32 elementy w posortowanej kolejności, z której wyszukujemy element za pomocą wyszukiwania binarnego.

1 2 3 4 5 6 ... 32

Załóżmy, że szukamy 32. po pierwszej iteracji zostaniemy z

17 18 19 20 .... 32

po drugiej iteracji zostaniemy z

25 26 27 28 .... 32

po trzeciej iteracji zostaniemy z

29 30 31 32

po czwartej iteracji zostaniemy z

31 32

W piątej iteracji znajdziemy wartość 32.

Tak więc, jeśli zamienimy to na równanie matematyczne, otrzymamy

(32 X (1/2 5 )) = 1

=> N X (2 -k ) = 1

=> (2 tys ) = n

=> k log 2 2 = log 2 n

=> k = log 2 n

Stąd dowód.


0

Oto rozwiązanie wykorzystujące twierdzenie główne, z czytelnym LaTeXem.

Dla każdego powtórzenia w relacji rekurencji dla wyszukiwania binarnego konwertujemy problem na jeden podproblem o czasie wykonywania T (N / 2). W związku z tym:

T (n) = T (n / 2) +1

Zastępując twierdzenie główne, otrzymujemy:

T (n) = aT (n / b) + f (n)

Teraz, ponieważ logbawynosi 0 if (n) wynosi 1, możemy użyć drugiego przypadku twierdzenia głównego, ponieważ:

f (n) = O (1) = O (n0) = O (nlogba)

To znaczy że:

T (n) = O (nlogbalogn) = O (n0logn) = O (logn)

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.