C'est le pseudo code que je veux calculer la complexité du temps, je pense que c'est un algorithme de recherche binaire mais j'échoue lors du calcul de la complexité car il réduit logarithamique.

   USE variables half-array,found,middle element
   SET half-array=initial array;
   SET found=True;

 Boolean SearchArray(half-array)

   find middle element in half-array;
   Compare search key with middle element;
   IF middle element==search key THEN
           SET found=True;
   ELSE
        IF search key< middle element THEN
          SET half-array=lower half of initial array;
        ELSE
          SET half-array=upper half of initial array;


 SearchArray(half-array)
-1
kalsara Magamage 26 avril 2017 à 16:46

3 réponses

Meilleure réponse

Il semble que vous exécutiez cette méthode de manière récursive, et à chaque itération, vous réduisez de moitié le nombre d'éléments recherchés. Cela va être une réduction logarithmique, c'est-à-dire O (log n) .

Puisque vous réduisez vos éléments de moitié à chaque fois, vous devez déterminer le nombre d'exécutions nécessaires pour le réduire à un seul élément, ce qui cette réponse précédente fournit une preuve ou si vous êtes une personne plus visuelle, vous pouvez utiliser le diagramme suivant de cette réponse:

enter image description here

3
Community 23 mai 2017 à 12:25

Vous avez raison de dire que cet algorithme est la recherche binaire (comparez votre pseudo code au pseudo code sur cette page Wikipédia: Recherche binaire)

Cela étant le cas, cet algorithme a une complexité temporelle du pire des cas de O (log n), où n est le nombre d'éléments dans le tableau donné. Cela est dû au fait que dans chaque appel récursif où vous ne trouvez pas l'élément cible, vous divisez le tableau en deux.

Ce processus de réduction est logarithmique car à la fin de cet algorithme, vous aurez réduit la liste à un seul élément en divisant le nombre d'éléments qui doivent encore être vérifiés par 2 - le nombre de fois que vous faites cela est à peu près équivalent (voir ci-dessous) au nombre de fois que vous auriez à multiplier 2 par lui-même pour obtenir un nombre égal à la taille du tableau donné.

* Je dis à peu près ci-dessus car le nombre d'appels récursifs effectués sera toujours une valeur intégrale, alors que la puissance que vous auriez à élever 2 ne sera pas un entier si la taille de la liste donnée n'est pas une puissance de deux.

0
Trevor Maliborski 26 avril 2017 à 14:05

Oui, il s'agit bien d'un algorithme de recherche binaire, la raison pour laquelle on l'appelle une recherche `` binaire '' est que, si vous aviez remarqué, après chaque itération, votre espace de problème est réduit d'environ la moitié (je dis en gros à cause du sol fonction). Alors maintenant, pour trouver la complexité, nous devons concevoir une relation de récurrence, que nous pouvons utiliser pour déterminer la complexité temporelle dans le pire des cas de la recherche binaire.

Soit T (n) le nombre de comparaisons effectuées par la recherche binaire pour n éléments. Dans le pire des cas, aucun élément n'est trouvé. Aussi, pour faciliter notre analyse, supposons que n est une puissance de 2

RECHERCHE BINAIRE:

  1. Lorsqu'il n'y a qu'un seul élément, il n'y a qu'une seule vérification, d'où T (1) = 1.

  2. Il calcule l'entrée du milieu puis la compare à notre clé.Si elle est égale à la clé, il renvoie l'index, sinon il divise par deux la plage en mettant à jour les bornes supérieure et inférieure de sorte que n / 2 éléments soient dans la plage.

  3. Nous vérifions ensuite une seule des deux moitiés, et cela se fait de manière récursive jusqu'à ce qu'un seul élément soit laissé.

Par conséquent, nous obtenons la relation de récurrence:

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

En utilisant le théorème maître, nous obtenons la complexité temporelle de T (n) ∈ Θ (log n)

Consultez également: Master Theorem

0
Ashwin Nalwade 26 avril 2017 à 14:04