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

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?

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 ₂ :

log ₂ (2 ^x ) = log ₂ N
x * log ₂ (2) = log ₂ N
x * 1 = log ₂ 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 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

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)

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.

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ę.

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 ¹ + N / 2 ² + N / 2 ³ + ..... + 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 ^x ) = log ₂ (N)
=> x * log ₂ (2) = log ₂ (N)
=> x * 1 = log ₂ (N)
=> Bardziej formalnie ⌊log ₂ (N) + 1⌋

Log2 (n) to maksymalna liczba wyszukiwań wymaganych do znalezienia czegoś w wyszukiwaniu binarnym. Przeciętny przypadek obejmuje wyszukiwania log2 (n) -1. Oto więcej informacji:

http://en.wikipedia.org/wiki/Binary_search#Performance

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)

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.

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)

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)

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

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 ⁵ )) = 1

=> N X (2 ^-k ) = 1

=> (2 ^tys ) = n

=> k log ₂ 2 = log ₂ n

=> k = log ₂ n

Stąd dowód.

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:

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

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

To znaczy że: