Discussion :

[carlesup3]

On me demande la chose suivante :

Quel est le coût en nombre de comparaisons de la recherche
dichotomique dans un tableau ?


1. Qu'est le coût d'un programme en général ? S'agit t-il d'un réel (j'ajoute cette question car il me semble qu'en TD on avait montré (enfin la prof l'a fait) que le coût de la suite de Fibonacci en additions était une puissance nième du nombre d'or).
2. Peut-on (je ne demande en aucun cas la réponse) vraiment donner une quantité précise ou bien cela dépend de la configuration du tableau?

Cordialement

[gasche]

La notion de coût généralement attendue est la "complexité algorithmique". Si tu n'en as jamais entendu parler avant, tu peux chercher sur internet, mais c'est un peu inquiétant, tu aurais du le voir en cours...

La complexité algorithmique est présentée comme un calcul, en fonction de la taille de l'entrée (pour une certaine définition de 'taille' qui dépend du problème), du nombre d'opérations totales effectuées, approximé à une constante multiplicative près -- on utilise les notations o(f) et O(f) que tu as peut-être vues en analyse.

Exemples de complexités classiques: linéaire O(n) (veut en fait dire O(n -> n), la fonction qui pour l'entrée de taille n fait n opérations), quadratique O(n^2) (veut en fait dire O(n -> n^2)), logarithmique O(log n), exponentielle (de facteur 2) O(2^n), etc.

On peut approximer par un nombre réel, oui. Notes cependant que pour Fibonacci, le nombre de calculs réels est toujours entier: c'est ((1+sqrt(5))/2)^n + ((1-sqrt(5))/2)^n. Si on oublie le deuxième terme qui est négligeable pour n grand, on obtient un réel, mais sinon c'est un entier.

[SpiceGuid]

Quel est le coût en nombre de comparaisons de la recherche
dichotomique dans un tableau ?
...
2. Peut-on (je ne demande en aucun cas la réponse) vraiment donner une quantité précise ou bien cela dépend de la configuration du tableau?

La recherche dichotomique est plus rapide que la recherche élément par élément. Toutefois la recherche dichotomique a un prérequis que n'a pas la recherche élément par élément, lequel ? Quel genre de relation doit exister dans l'ensemble des éléments pour pouvoir satisfaire ce prérequis ?