Algo de classement
Re: Algo de classement
Bonjour,
Le terme exact est plus algorithme de tri que algorithme de classement.
Il me semble que ce que tu as en tête pourrait être un tri arborescent qui consiste à insérer successivement chacun des n éléments dans un arbre binaire de recherche. Tu as dans ce cas une complexité en moyenne en O(n * ln (n)) comparaisons, puisque pour chacun des n éléments tu dois trouver sa place dans l'ABR ce qui a une complexité en ln(n).
C'est donc effectivement meilleur que la première méthode qui me semble être un tri par sélection pour lequel tu vas faire n*(n-1)/2 comparaisons et donc une complexité en O(n²).
Le terme exact est plus algorithme de tri que algorithme de classement.
Il me semble que ce que tu as en tête pourrait être un tri arborescent qui consiste à insérer successivement chacun des n éléments dans un arbre binaire de recherche. Tu as dans ce cas une complexité en moyenne en O(n * ln (n)) comparaisons, puisque pour chacun des n éléments tu dois trouver sa place dans l'ABR ce qui a une complexité en ln(n).
C'est donc effectivement meilleur que la première méthode qui me semble être un tri par sélection pour lequel tu vas faire n*(n-1)/2 comparaisons et donc une complexité en O(n²).
Re: Algo de classement
Il s'agit effectivement d'un algorithme de tri par comparaisons. Beaucoup existent avec des avantages ou des inconvénients, mais on peut raisonnablement montrer qu'on ne peut pas espérer faire moins de O(n ln n) comparaisons.
Si on considère l'arbre binaire dont les nœuds sont les comparaisons effectuées et les feuilles sont les classements complets, alors la hauteur maximale h de l'arbre correspond au nombre maximal de comparaisons, et limite le nombre de feuilles à 2^h. Par ailleurs, chacune des n! permutations doit figurer sur une feuille, ce qui donne donc 2^h > n! d'où (...) h > n/2 log_2(n/2).
Si on considère l'arbre binaire dont les nœuds sont les comparaisons effectuées et les feuilles sont les classements complets, alors la hauteur maximale h de l'arbre correspond au nombre maximal de comparaisons, et limite le nombre de feuilles à 2^h. Par ailleurs, chacune des n! permutations doit figurer sur une feuille, ce qui donne donc 2^h > n! d'où (...) h > n/2 log_2(n/2).
Re: Algo de classement
Ca n'aide pas beaucoup à comprendre le pourquoi je trouvepuisque pour chacun des n éléments tu dois trouver sa place dans l'ABR ce qui a une complexité en ln(n).
.Il y a 2^N classements possibles.
Un choix permet de sélectionner une alternative parmi 2.
On calcule donc facilement le nombre minimal de choix (comparaisons) qu'il va falloir effectuer....et ça explique facilement le 'n log n'
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: Algo de classement
Pour n tableaux il y a n! permutations dont une seule (par hypothèse) représente le classement ordonné des tableaux par beauté. Une preuve que j'aime bien est celle qui utilise la théorie de l'information.
Une comparaison (ou question à deux choix) te donne un bit d'information. Donc le nombre de comparaisons nécessaires pour discriminer la bonne permutation est logbase2(n!) \equiv n ln(n) / ln(2). Donc effectivement un algorithme de tri basé sur des comparaisons que le PO évoque bien a une complexité asymptotique en comparaisons en O(n log n) (qui vaut aussi dans le pire cas) comme l'ont dit les autres, ce qui équivaut à descendre un arbre binaire complet, dont la profondeur est aussi de l'ordre de O(n log n) pour représenter n! permutations, c'est un résultat bien connu.
Le tri fusion est un algorithme présentant la complexité asymptotique optimale pour ce problème.
C'est bizarre que tu n'aies pas trouvé en cherchant, ce résultat est dans tous les livres d'informatique, je pense que tu n'as pas dû utiliser les bons mots clés. Pour une entrée en matière, wikipédia (anglais c'est mieux souvent) donne de bonnes idées et sources.
[que qqn me corrige si j'ai raconté des ânneries qqpart]
Une comparaison (ou question à deux choix) te donne un bit d'information. Donc le nombre de comparaisons nécessaires pour discriminer la bonne permutation est logbase2(n!) \equiv n ln(n) / ln(2). Donc effectivement un algorithme de tri basé sur des comparaisons que le PO évoque bien a une complexité asymptotique en comparaisons en O(n log n) (qui vaut aussi dans le pire cas) comme l'ont dit les autres, ce qui équivaut à descendre un arbre binaire complet, dont la profondeur est aussi de l'ordre de O(n log n) pour représenter n! permutations, c'est un résultat bien connu.
Le tri fusion est un algorithme présentant la complexité asymptotique optimale pour ce problème.
C'est bizarre que tu n'aies pas trouvé en cherchant, ce résultat est dans tous les livres d'informatique, je pense que tu n'as pas dû utiliser les bons mots clés. Pour une entrée en matière, wikipédia (anglais c'est mieux souvent) donne de bonnes idées et sources.
[que qqn me corrige si j'ai raconté des ânneries qqpart]