/ / Relacja relacji liczby porównań w wyszukiwaniu binarnym - algorytm, wyszukiwanie binarne, rekurencja

Relacja relacji liczby porównań w wyszukiwaniu binarnym - algorytm, wyszukiwanie binarne, rekurencja

Mam wątpliwość co do relacji nawrotów dla liczby porównań w wyszukiwaniu binarnym.

Czytałem, że powtarzanie można zapisać jako T (n) = T (n / 2) + 1 na tej stronie http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L14-RecRel.htm

Według mnie powinno to być T (n) = T (n / 2) + 2, ponieważ w najgorszym przypadku element może nie być obecny w macierzy iw efekcie wykonujemy 2 porównania w każdym przebiegu.

Proszę powiedz mi, czy mam rację, czy nie.

Odpowiedzi:

1 dla odpowiedzi № 1

Myślę, że masz rację.

MOIM ZDANIEM, compare a b oznacza, że ​​wiemy a=b, a>b lub a<b w tym samym czasie. To znaczy, 1 porównanie może mieć 3 różne wyniki.

Ale w przypadku języków programowania. Musimy użyć 2 porównań.

if mid == x:      found it!          # 1st
else if mid < x:  search right       # 2nd
else:             search left

Masz na myśli == i < są 2 porównania.

Nie wpływa to jednak na wynik. Ponieważ używamy wielkiej notacji O, aby przedstawić złożoność. To tylko kwestia stałej, ale O zwykle nie dbają o to.

Według główne twierdzenie. Zarówno +1 lub +2 spowoduje taką samą złożoność O(log n).

To, czego chcemy, to zwykle limit (Big-O), a nie matematyczny wynik dokładnego równania.

Myślę, że tutaj liczy się to 1 i 2 są stałym czasem. Możemy również podzielić ==, > do instrukcji maszynowych i może być większy niż 2. A może niektóre języki programowania lub procesory wykorzystują porównanie, to tylko kosztuje 1 porównanie. Ale to nie ma znaczenia przy analizie asymptotycznej.


  1. https://en.wikipedia.org/wiki/Master_theorem
  2. https://en.wikipedia.org/wiki/Asymptotic_analysis