Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente | |||
info:algo:complexite [2021/08/10 11:32] – phil | info:algo:complexite [2021/08/11 09:19] (Version actuelle) – modification externe 127.0.0.1 | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | {{ : | ||
+ | |||
+ | ===== Complexité d'un algorithme ===== | ||
+ | |||
+ | < | ||
+ | |||
+ | **Source** : Données et algorithmes (Mooc Fun) | ||
+ | |||
+ | **Contexte** : recherche d'un mots dans un tableau. | ||
+ | |||
+ | ==== Cas 1 : tableau non trié (recherche exhaustive ou par force brute) ==== | ||
+ | // | ||
+ | - Pour tester la présence d’un mot, on le compare au premier élément du tableau, puis le cas échéant au second, au troisième etc. L' | ||
+ | - On a trouvé le mot à l' | ||
+ | - On a atteint la fin du tableau sans trouver le mot. | ||
+ | |||
+ | // | ||
+ | |||
+ | A faire | ||
+ | |||
+ | // | ||
+ | |||
+ | Le point important dans l’évaluation du temps d' | ||
+ | |||
+ | Deux cas possibles : | ||
+ | * Si le mot est correct, alors le stockage aléatoire des mots dans le tableau fait que la probabilité de trouver le mot à n’importe quelle place dans le tableau est la même : en moyenne, on fera donc **N/2 comparaisons** (i.e. le mot est en moyenne au milieu du tableau). | ||
+ | * Si le mot n’est pas correct, alors on dois tester tous les éléments du tableau soit **N comparaisons**. | ||
+ | |||
+ | <note important> | ||
+ | |||
+ | ==== Cas 2: tableau trié (recherche par dichotomie) ==== | ||
+ | // | ||
+ | |||
+ | On compare le mot cherché à l’élément central du tableau. | ||
+ | * Si le mot cherché est avant l’élément central, on sait qu'il suffit de regarder dans la première moitié du tableau. | ||
+ | * Symétriquement, | ||
+ | |||
+ | // | ||
+ | |||
+ | A faire | ||
+ | |||
+ | // | ||
+ | |||
+ | Le point important ici est que, dans les deux cas où on échoue, la moitié des éléments du tableau a été éliminé. Si l’on répète l’opération ci-dessus sur la moitié restante, il nous restera au pire un quart du tableau initial ; si on la répète à nouveau (pour la troisième fois donc), il restera un huitième du tableau initial, etc : la taille du tableau restant diminue d’un facteur 2 à chaque comparaison ! | ||
+ | |||
+ | On voit donc que pour **i comparaisons**, | ||
+ | |||
+ | === Performance comparée des deux méthodes ==== | ||
+ | On effectue les tests sur un tableau de 100000 mots. On suppose que le temps nécessaire à la comparaison de deux mots est de 1ms. \\ | ||
+ | On se place dans la situation la plus favorable. | ||
+ | * **Cas 1** : t = N/2 x tc = (10< | ||
+ | * **Cas 2** : t = log< | ||