Le tri par tas : Différence entre versions
De Sciencinfolycee
Ligne 7 : | Ligne 7 : | ||
|Résumé=Algorithme de tri par comparaison qui est de complexité asymptotiquement optimale car de complexité O(n log n). À la différence du tri par insertion où lorsque l'on double la taille de l'entrée, on multiplie par 4 le nombre d'opérations effectuées par l'algorithme, le tri par tas ne multipliera, dans les mêmes circonstances, qu'environ par 2 (un peu plus en réalité, mais lorsque n est grand c'est négligeable) le nombre d'opérations. | |Résumé=Algorithme de tri par comparaison qui est de complexité asymptotiquement optimale car de complexité O(n log n). À la différence du tri par insertion où lorsque l'on double la taille de l'entrée, on multiplie par 4 le nombre d'opérations effectuées par l'algorithme, le tri par tas ne multipliera, dans les mêmes circonstances, qu'environ par 2 (un peu plus en réalité, mais lorsque n est grand c'est négligeable) le nombre d'opérations. | ||
|Catégorie=1.4. Algorithmes classiques | |Catégorie=1.4. Algorithmes classiques | ||
− | |Mots-clés contrôlés= | + | |Mots-clés contrôlés=arbre binaire; algorithme de tri; tri par tas; file : informatique; |
|SiloTypeDocumentaire=texte | |SiloTypeDocumentaire=texte | ||
|SiloTypologieGenerale=article | |SiloTypologieGenerale=article | ||
− | |Date= | + | |Date=1970/01/01 |
|SiloStructure=atomique | |SiloStructure=atomique | ||
|SiloNiveauAgregation=1.Le plus petit niveau (grain) | |SiloNiveauAgregation=1.Le plus petit niveau (grain) |
Version du 19 septembre 2011 à 08:45
Section Description | |
---|---|
URL | http://www.siteduzero.com/tutoriel-3-261748-le-tri-par-tas.html |
Titre | Le tri par tas |
Auteur(s) | Site du Zéro |
Fonction(s) | diffuseur/ distributeur |
Notes | |
Section Analyse | |
Langue | fre |
Résumé | Algorithme de tri par comparaison qui est de complexité asymptotiquement optimale car de complexité O(n log n). À la différence du tri par insertion où lorsque l'on double la taille de l'entrée, on multiplie par 4 le nombre d'opérations effectuées par l'algorithme, le tri par tas ne multipliera, dans les mêmes circonstances, qu'environ par 2 (un peu plus en réalité, mais lorsque n est grand c'est négligeable) le nombre d'opérations. |
Sélection(s) thématique(s) | 1.4. Algorithmes classiques |
Mots-clés normalisés | arbre binaire ; algorithme de tri ; tri par tas« tri par tas » n'est pas la liste (2D, 3D, 4D, abstraction de périphérique, abstraction des systèmes d'exploitation, accéléromètre, Ackermann, Wilhelm : 1896-1962, actionneur, actionneur orienté homme, ActionScript, ...) des valeurs autorisées pour la propriété « Mot-cle normalise » . ; file : informatique |
Proposition autres mots-clés | |
Type documentaire | texte |
Typologie Générale | article |
Date de publication | 1970/01/01 |
Structure du document | atomique |
Niveau d'agrégation | 1.Le plus petit niveau (grain) |
Exigences techniques | |
Section Pédagogie | |
Type pédagogique | cours / présentation |
Public cible | enseignant |
Utilisation pédagogique | |
Section Relation | |
Type de la relation | est une partie de |
URL de la relation | http://www.siteduzero.com/tutoriel-2-217-algorithmique.html |
Section Droits | |
Droits du document | |
Section processus de validation (workflow) | |
Intervenants | Thierry; Diane Rives (indexation); DB |
Statut du workflow | publiée |
Signaler cette ressource. Si ce lien de signalement ne fonctionne pas (ouverture intempestive d'un mailer alors que vous utilisez un webmail) c'est qu'il vous manque l'extension idoine dans votre navigateur (par exemple l'extension send-mail pour firefox); c'est une bonne occasion de l'installer.