Algo de classement

Messages : 1

Inscription : 15 mai 2019 23:06

Profil de l'utilisateur : Élève de lycée

Algo de classement

Message par tomdalton6868 » 13 févr. 2022 12:28

-
Dernière modification par tomdalton6868 le 27 mai 2023 10:28, modifié 1 fois.

Messages : 187

Inscription : 09 août 2018 20:57

Profil de l'utilisateur : Élève de lycée

Re: Algo de classement

Message par GrosGillouDu92 » 13 févr. 2022 13:14

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²).

Messages : 3

Inscription : 16 janv. 2022 10:41

Profil de l'utilisateur : Élève de lycée

Re: Algo de classement

Message par emeric.tourniaire » 14 févr. 2022 23:47

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).

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: Algo de classement

Message par fakbill » 28 févr. 2022 10:22

puisque pour chacun des n éléments tu dois trouver sa place dans l'ABR ce qui a une complexité en ln(n).
Ca n'aide pas beaucoup à comprendre le pourquoi je trouve :(.
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é.

Messages : 38

Inscription : 01 nov. 2021 21:16

Profil de l'utilisateur : Élève de lycée

Re: Algo de classement

Message par chamaerops » 07 août 2022 12:41

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]

Répondre