comment calculer la complexité de la recherche binaire

J'ai entendu quelqu'un dire que puisque la recherche binaire divise par deux l'entrée requise pour la recherche, c'est donc l'algorithme log (n). Comme je ne suis pas d'origine mathématique, je ne suis pas en mesure de m'y rattacher. Quelqu'un peut-il l'expliquer un peu plus en détail? doit-il faire quelque chose avec la série logarithmique?

Voici une façon plus mathématique de le voir, mais pas vraiment compliqué. IMO beaucoup plus clair que les informels:

La question est, combien de fois pouvez-vous diviser N par 2 jusqu'à ce que vous en ayez 1? Cela signifie essentiellement, effectuez une recherche binaire (la moitié des éléments) jusqu'à ce que vous l'ayez trouvé. Dans une formule, ce serait ceci:

1 = N / 2 ^x

multipliez par 2 ^x :

2 ^x = N

maintenant, faites le journal ₂ :

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

cela signifie que vous pouvez diviser le journal N fois jusqu'à ce que tout soit divisé. Ce qui signifie que vous devez diviser le journal N ("faire l'étape de recherche binaire") jusqu'à ce que vous trouviez votre élément.

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 (une base b) = 1

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

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

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

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

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

Mettez la valeur de The (n / 2) ci-dessus pour que 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

La complexité du temps est donc O (log n)

Ce n'est pas la moitié du temps de recherche, cela ne le ferait pas enregistrer (n). Il le diminue de manière logarithmique. Pensez à cela pendant un moment. Si vous aviez 128 entrées dans une table et que vous deviez rechercher votre valeur de manière linéaire, il faudrait probablement environ 64 entrées en moyenne pour trouver votre valeur. C'est n / 2 ou temps linéaire. Avec une recherche binaire, vous éliminez la moitié des entrées possibles à chaque itération, de sorte qu'au plus il ne faudrait que 7 comparaisons pour trouver votre valeur (la base log 2 de 128 est 7 ou 2 à la puissance 7 est 128.) C'est la puissance de la recherche binaire.

La complexité temporelle de l'algorithme de recherche binaire appartient à la classe O (log n). On appelle cela grande notation O . La façon dont vous devez interpréter cela est que la croissance asymptotique du temps que la fonction prend pour s'exécuter étant donné un ensemble d'entrée de taille n ne dépassera paslog n .

Ceci est juste un jargon mathématique formel afin de pouvoir prouver des déclarations, etc. Il a une explication très simple. Lorsque n devient très grand, la fonction log n augmentera plus le temps nécessaire pour exécuter la fonction. La taille du "jeu d'entrées", n, est juste la longueur de la liste.

En termes simples, la raison pour laquelle la recherche binaire est en O (log n) est qu'elle divise par deux le jeu d'entrées à chaque itération. Il est plus facile d'y penser dans la situation inverse. Sur x itérations, combien de temps l'algorithme de recherche binaire peut-il examiner au maximum? La réponse est 2 ^ x. De cela, nous pouvons voir que l'inverse est qu'en moyenne l'algorithme de recherche binaire a besoin de log2 n itérations pour une liste de longueur n.

Si pourquoi c'est O (log n) et non O (log2 n), c'est parce que simplement répété - L'utilisation des grandes constantes de notation O ne compte pas.

Voici l' entrée wikipedia

Si vous regardez l'approche itérative simple. Vous éliminez simplement la moitié des éléments à rechercher jusqu'à ce que vous trouviez l'élément dont vous avez besoin.

Voici l'explication de la manière dont nous élaborons la formule.

Dites d'abord que vous avez N nombre d'éléments, puis ce que vous faites est «N / 2» comme première tentative. Où N est la somme de la borne inférieure et de la borne supérieure. La première valeur temporelle de N serait égale à (L + H), où L est le premier index (0) et H est le dernier index de la liste que vous recherchez. Si vous avez de la chance, l'élément que vous essayez de trouver sera au milieu [par exemple. Vous cherchez 18 dans la liste {16, 17, 18, 19, 20} puis vous calculez ⌊ (0 + 4) / 2⌋ = 2 où 0 est la borne inférieure (L - index du premier élément du tableau) et 4 est la borne supérieure (H - indice du dernier élément du tableau). Dans le cas ci-dessus L = 0 et H = 4. Maintenant, 2 est l'indice de l'élément 18 que vous recherchez. Bingo! Tu l'as trouvé.

Si le cas était un tableau différent {15,16,17,18,19} mais que vous recherchiez toujours 18, vous n'auriez pas de chance et vous feriez d'abord N / 2 (qui est ⌊ (0 + 4) / 2⌋ = 2 puis réalisez que l'élément 17 à l'index 2 n'est pas le nombre que vous recherchez. Vous savez maintenant que vous n'avez pas à rechercher au moins la moitié du tableau lors de votre prochaine tentative de recherche de manière itérative. l'effort de recherche est divisé par deux. Donc, fondamentalement, vous ne recherchez pas la moitié de la liste des éléments que vous avez recherchés précédemment, chaque fois que vous essayez de trouver l'élément que vous n'avez pas pu trouver lors de votre précédente tentative.

Donc le pire des cas serait

[N] / 2 + [(N / 2)] / 2 + [((N / 2) / 2)] / 2 .....
soit:
N / 2 ¹ + N / 2 ² + N / 2 ³ + ..... + N / 2 ^x … ..

jusqu'à ce que ... vous ayez terminé la recherche, où dans l'élément que vous essayez de trouver se trouve à la fin de la liste.

Cela montre que le pire des cas est lorsque vous atteignez N / 2 ^x où x est tel que 2 ^x = N

Dans les autres cas N / 2 ^x où x est tel que 2 ^x <N La valeur minimale de x peut être 1, ce qui est le meilleur des cas.

Or, puisque le pire des cas mathématiques est celui où la valeur de
2 ^x = N
=> log ₂ (2 ^x ) = log ₂ (N)
=> x * log ₂ (2) = log ₂ (N)
=> x * 1 = log ₂ (N)
=> Plus formellement ⌊log ₂ (N) + 1⌋

Log2 (n) est le nombre maximum de recherches nécessaires pour trouver quelque chose dans une recherche binaire. Le cas moyen implique des recherches log2 (n) -1. Voici plus d'informations:

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

Disons que l'itération dans la recherche binaire se termine après k itérations. À chaque itération, le tableau est divisé par moitié. Supposons donc que la longueur du tableau à toute itération soit n à l'itération 1,

Length of array = n

À l'itération 2,

Length of array = n⁄2

À l'itération 3,

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

Par conséquent, après l'itération k,

Length of array = n⁄2k

De plus, nous savons qu'après k divisions, la longueur du tableau devient 1 Par conséquent

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

Application de la fonction de journal des deux côtés:

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

Par conséquent,

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

Par conséquent, la complexité temporelle de la recherche binaire est

log2 (n)

Une recherche binaire fonctionne en divisant le problème en deux à plusieurs reprises, quelque chose comme ceci (détails omis):

Exemple de recherche de 3 dans [4,1,3,8,5]

1. Commandez votre liste d'articles [1,3,4,5,8]
2. Regardez l'élément du milieu (4),
   • Si c'est ce que vous cherchez, arrêtez
   • S'il est plus grand, regardez la première moitié
   • Si c'est moins, regardez la seconde moitié
3. Répétez l'étape 2 avec la nouvelle liste [1, 3], trouvez 3 et arrêtez

C'est un bi recherche annuelle lorsque vous divisez le problème en 2.

La recherche ne nécessite que des étapes log2 (n) pour trouver la valeur correcte.

Je recommanderais Introduction aux algorithmes si vous souhaitez en savoir plus sur la complexité algorithmique.

Puisque nous réduisons une liste de moitié à chaque fois, nous avons donc juste besoin de savoir en combien d'étapes nous obtenons 1 lorsque nous divisons une liste par deux. Dans le calcul ci-dessous, x désigne le nombre de fois où nous divisons une liste jusqu'à ce que nous obtenions un élément (dans le pire des cas).

1 = N / 2x

2x = N

Prendre 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 (base 2 log) = 1 + logN

La complexité temporelle de la recherche binaire est donc 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

Permettez-moi de vous faciliter la tâche à tous avec un exemple.

Par souci de simplicité, supposons qu'il y ait 32 éléments dans un tableau dans l'ordre trié dans lequel nous recherchons un élément à l'aide de la recherche binaire.

1 2 3 4 5 6 ... 32

Supposons que nous recherchons 32. après la première itération, il nous restera

17 18 19 20 .... 32

après la deuxième itération, il nous restera

25 26 27 28 .... 32

après la troisième itération, il nous restera

29 30 31 32

après la quatrième itération, il nous restera

31 32

Dans la cinquième itération, nous trouverons la valeur 32.

Donc, si nous convertissons cela en une équation mathématique, nous obtiendrons

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

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

=> (2 ^k ) = n

=> k log ₂ 2 = log ₂ n

=> k = log ₂ n

D'où la preuve.

Voici la solution utilisant le théorème maître, avec LaTeX lisible.

Pour chaque récurrence dans la relation de récurrence pour la recherche binaire, nous convertissons le problème en un sous-problème, avec le temps d'exécution T (N / 2). Par conséquent:

En se substituant au théorème maître, on obtient:

Maintenant, comme est 0 et f (n) est 1, nous pouvons utiliser le deuxième cas du théorème maître car:

Cela signifie que: