Quel est le meilleur algorithme de tri à inclure dans une bibliothèque (et donc pas pour un besoin spécifique mais en général) ?
Avec des notions de base en complexité, on peut calculer la complexité au pire de Quicksort, O(n^2) et celle de Mergesort O(n * log n), et en déduire que Mergesort est meilleur.
Si on arrive à calculer la complexité en moyenne, on se rend compte que Quickstort, en moyenne, est en O(n * log n), et si on investigue un peu on se rendra compte qu'en pratique il est en général plus rapide.
C'est un exemple classique qui explique pourquoi la complexité au pire n'est pas toujours suffisante pour choisir un algorithme. Et calculer la complexité en moyenne d'un algorithme, c'est souvent une autre paire de manches. J'ai eu à prouver celle de Mergesort en DEA...
En fait, j'ai l'impression que pour toi un "besoin pratique de l'informatique", ça sera plutôt d'ouvrir un livre, regarder les différentes complexités et savoir reconnaitre laquelle est la meilleure. Effectivement dans ce cas, il suffit de savoir qu'un logarithme est meilleur qu'une exponentielle.
[^] # Re: sonntag
Posté par Yusei (Mastodon) . En réponse à la dépêche Lisaac 0.12 en GPL v3. Évalué à 2.
Avec des notions de base en complexité, on peut calculer la complexité au pire de Quicksort, O(n^2) et celle de Mergesort O(n * log n), et en déduire que Mergesort est meilleur.
Si on arrive à calculer la complexité en moyenne, on se rend compte que Quickstort, en moyenne, est en O(n * log n), et si on investigue un peu on se rendra compte qu'en pratique il est en général plus rapide.
C'est un exemple classique qui explique pourquoi la complexité au pire n'est pas toujours suffisante pour choisir un algorithme. Et calculer la complexité en moyenne d'un algorithme, c'est souvent une autre paire de manches. J'ai eu à prouver celle de Mergesort en DEA...
En fait, j'ai l'impression que pour toi un "besoin pratique de l'informatique", ça sera plutôt d'ouvrir un livre, regarder les différentes complexités et savoir reconnaitre laquelle est la meilleure. Effectivement dans ce cas, il suffit de savoir qu'un logarithme est meilleur qu'une exponentielle.