comment calculer la complexité de la recherche binaire

Question

J'ai entendu quelqu'un dire que puisque la recherche binaire réduit de moitié l'entrée requise pour la recherche, il s'agit donc de l'algorithme log(n). Comme je ne suis pas issu d'un milieu mathématique, je ne suis pas en mesure de m'identifier à cela. Quelqu'un peut-il l'expliquer un peu plus en détail? Cela a-t-il un rapport avec la série logarithmique ?

Answer 1

Pour la recherche binaire, T(N) = T(N/2) + O(1) // la relation de récurrence

Appliquer le théorème de maîtrise pour le calcul de la complexité d'exécution des relations de récurrence : T(N) = aT(N/b) + f(N)

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

aussi, ici f(N) = n^c log^k(n) //k = 0 & c = log (a base b)

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

Source : http://en.wikipedia.org/wiki/Master_theorem

Answer 2

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

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

Mettez la valeur de The(n/2) ci-dessus donc T(n)=T(n/4)+1+1 . . . . T(n/2^k)+1+1+1.....+1

=T(2^k/2^k)+1+1....+1 jusqu'à k

=T(1)+k

Comme nous avons pris 2^k=n

K = log n

Donc la complexité temporelle est O(log n)