Fusion de la complexité du temps de tri
Division entier par deux
La division entière est nécessaire lors d'un tri de fusion.
Lorsqu'un nombre impair est divisé par deux, il y a un reste de 1. Par exemple:
7/2 = 3 r 1
La division entière signifie prendre tout le nombre comme réponse et abandonner le 1.
Lorsqu'un nombre uniforme est divisé par deux, il y a un reste de 0. Par exemple:
6/2 = 3 r 0
La division entière signifie prendre tout le nombre comme votre réponse et abandonner le 0.
Dans les deux cas, le nombre total est pris et le reste est abandonné.
L'objectif de cet article est de déterminer la complexité temporelle du tri de fusion, également écrite comme Mergesort. Le tri peut ascendant ou descendre. Le tri dans cet article fait référence à la tri.
Algorithme de tri de fusion
Merge Sort est un algorithme de tri Divide and Conquérer. Dans cet algorithme, la liste non triée est divisée en deux moitiés en utilisant la division entier. Chacune des moitiés est encore divisée en deux moitiés à nouveau en utilisant la division entier. Cette division se poursuit jusqu'à ce que la liste soit considérée comme des éléments distincts uniques.
À partir de la gauche, les éléments consécutifs sont ensuite jumelés de manière triée. Les éléments appariés sont ensuite appariés à nouveau sous une forme triée. Ce regroupement par paires se poursuit jusqu'à ce que toute la liste soit réformée et triée.
Complexité temporelle linéaire et logarithmique
Considérez le code suivant dans la langue C:
pour (int i = 0; i<8; i++)
int k = i + 1;
printf ("% d", k);
printf ("\ n");
La sortie est:
1 2 3 4 5 6 7 8
Le code est une boucle pour (ignorer la déclaration d'impression juste après la boucle pour la boucle). Il imprime les entiers de 1 à 8, pour un total de 8 numéros. Le contenu du corps de la boucle est:
int k = i + 1;
printf ("% d", k);
Ces deux déclarations sont considérées comme une opération principale dans cette situation. Il y a 8 opérations. Soit n être 8. Il s'agit d'une complexité temporelle linéaire et elle est écrite comme suit:
Sur)
Où n est le nombre maximum d'opérations possible. C'est la notation Big-O. Il commence par O en majuscules et suivi de parenthèses. À l'intérieur des parenthèses se trouve le nombre maximal possible d'opérations.
Considérez maintenant le code suivant où sur 8 numéros, 3 numéros sont imprimés:
pour (int i = 0; i<8; i++)
int k = i + 1;
printf ("% d", k);
si (k == 3) casser;
printf ("\ n");
La sortie est:
1 2 3
Le code est une boucle pour (ignorer la déclaration d'impression juste après la boucle pour la boucle). Il imprime les entiers de 1 à 3 sur 8 numéros. Le contenu du corps de la boucle est:
int k = i + 1;
printf ("% d", k);
si (k == 3) casser;
Pourtant, ces trois déclarations sont considérées comme une opération principale dans cette situation. Il y a 3 opérations sur 8.
Maintenant,
8 = 23
=> 3 = journal2(8)
Ainsi, le nombre d'opérations principales effectuées par le code précédent est de 3 (sur 8).
Soit n être 8. Il s'agit d'une complexité temporelle logarithmique et elle est écrite comme:
O (journal2n)
Où (journalisation2 n) signifie 3 pour le code précédent.
Il y avait 8 nombres. En général, lorsque le nombre d'opérations pour le code se situe entre 2 et 5 sur 8 et pas seulement 3, la complexité temporelle est décrite comme le journal2(n).
Exemple de liste non triée et triée
Un exemple de liste non triée est la suivante:
P V D Q S X T B
Il y a huit éléments dans la liste. Lorsque cette liste est triée, elle devient:
B d p q s t v x
Compter le nombre d'opérations principales dans le tri de fusion
La liste suivante:
P V D Q S X T B
est utilisé pour compter le nombre des principales opérations en sort de fusion.
La division entière de deux donne le résultat suivant:
P V D Q S X T B
C'est une opération. Une autre division des deux parties de deux donne le résultat suivant:
P V D Q S X T B
Ce sont trois opérations jusqu'à présent (un plus deux). Une autre division de chaque nouvelle partie par deux donne le résultat suivant:
P V D Q S X T B
Ce sont sept opérations jusqu'à présent (trois plus quatre). La liste des huit éléments est désormais considérée comme huit éléments distincts avec un total de sept opérations jusqu'à présent. La phase suivante consiste à coupler pendant le tri, à partir de la gauche. Donc, le résultat suivant est:
P V D Q S X B T
Il y a deux changements de position pour la dernière paire. Deux changements sont deux opérations. Cela fait jusqu'à présent un total de neuf opérations (sept plus deux).
L'appariement et le tri se poursuivent, en commençant toujours de la gauche pour donner le résultat suivant:
D P Q V B S T X
Chacun de ces deux groupes a eu quatre changements de position, faisant huit opérations. Il y a jusqu'à présent dix-sept opérations (neuf plus huit). L'appariement et le tri se poursuivent et enfin, pour donner le résultat suivant:
B d p q s t v x
Il y a sept changements de position ici, faisant sept opérations. Cela fait vingt-quatre opérations (dix-sept plus sept) pour le tri complet.
Complexité du temps pour la fusion
Le comptage précédent (illustration) est utilisé pour citer la complexité temporelle du Mergesort. Il y a vingt-quatre opérations.
24 = 8 x 3
C'est-à-dire:
24 = 8 x journal2(8)
Parce que log2 (8) est 3.
Soit 8 n. Avec cela, la complexité du temps de Mergesort est donnée par:
Sur.enregistrer2n)
où le point signifie multiplication.
En pratique, sur 8 éléments, le nombre d'opérations est d'environ 24 ou 24.
Conclusion
Le Mergesort est un algorithme de tri de division et de conquête particulier. C'est un algorithme de tri très efficace. Sa complexité temporelle est très satisfaisante par rapport aux autres algorithmes de tri. Sa complexité du temps est:
O (nlog2n)
Remarque: le nombre d'opérations ne doit pas nécessairement être exactement n.log2n . Cependant, il devrait l'approximer.
Le codage Mergesort a besoin de fonctions récursives. Il n'est pas trop difficile de le coder une fois l'algorithme compris. Le codage du tri de fusion est une discussion pour une autre fois.