Comment déterminez-vous la notation Big-O d'une boucle while?

Question

Voici une fonction de recherche binaire.

int search(int a[], int v, int left, int right) 
{ 
    while (right >= left) 
    { 
     int m = (left + right)/2; 
     if (v == a[m]) 
      return m; 
     if (v < a[m]) 
      right = m - 1; 
     else left = m + 1; 
    } 
    return -1; 
} 

Comment déterminer la notation Big-O pour cette fonction?

Cette fonction de recherche est-elle O (n) puisque la boucle while dépend de la valeur left?

Answer 1

Dans chaque étape, la plage de demi-valeurs (à peu près) - si vous commencez avec right - left == 100, puis à la deuxième étape, il sera 49, puis 24, puis 11, etc.

En supposant n = right - left, la complexité est O (log n). (Cela dépend des valeurs de droite et de gauche.)

Answer 2

Jon Skeet déjà answered la question.

Ici, je montre comment nous pouvons le résoudre mathématiquement.

Comme dans chaque boucle nous réduisons la plage de moitié, dans le pire des cas nous aurons besoin de steps itérations au maximum. Comment calculer le numéro steps?

"Réduire de moitié la gamme" peut être exprimée en: plage/2 ^étapes

Nous pouvons continuer de réduire de moitié jusqu'à ce que range devient .
Ainsi, l'équation est la suivante: gamme/2 ^étapes = 1

Solution:
lg (portée/2 ^étapes) = lg (1)
lg (plage) - étapes * lg (2) = 0

étapes = lg (plage), où lg est le logarithme de ba se 2.