Le tri rapide est un algorithme de tri développé par Tony Hall. En moyenne, le tri de n objets nécessite une comparaison de n logn. Dans le pire des cas, il faut une comparaison de n 2, mais ce n'est pas courant. En fait, le tri rapide est généralement nettement plus rapide que les autres algorithmes de n logn, car sa boucle interne peut être mise en œuvre très efficacement sur la plupart des architectures.
L'ordre rapide utilise la stratégie Divideandconquer pour diviser une liste en deux sous-listes.
Les étapes de l'algorithme
1, choisir un élément de la colonne numérique, appelé pivot,
2° réorganiser la colonne, en plaçant tous les éléments inférieurs à la valeur de référence devant la référence et tous les éléments supérieurs à la valeur de référence derrière la référence (le même nombre peut aller de part et d'autre); après avoir quitté cette partition, la référence est au milieu de la colonne; cela s'appelle une opération de partition.
3, récursive: ordonne les sous-catégories des éléments inférieurs à la valeur de référence et des éléments supérieurs à la valeur de référence.
Le cas le plus bas de la récursion est que la taille de la rangée est zéro ou un, c'est-à-dire qu'elle a toujours été bien classée. Bien qu'elle continue de récurrer, l'algorithme s'écarte toujours, car à chaque itération, il met au moins un élément à sa dernière position.
Le heapsort est un algorithme de tri conçu pour exploiter une structure de données de ce type. Le heapsort est une structure presque entièrement binaire qui satisfait à la propriété du heapsort: la valeur de la clé ou de l'index d'un nœud est toujours inférieure ou supérieure à celle de son nœud parent.
La complexité de temps moyenne de l'ordre de la pile est O (nlogn).
Les étapes de l'algorithme
1, créer une pile H [0... n - 1 ]
2, remplacer la tête (max) et la queue
3, réduire la taille de la pile de 1 et appeler Shift_down ((0), afin d'ajuster les données du nouveau sommet de l'arithmétique à la position appropriée
4, répétez l'étape 2 jusqu'à ce que la taille de la pile soit 1.
Mergesort est un algorithme de tri efficace basé sur l'opération d'association. Il est une application très typique de la méthode de division et conquête.
Les étapes de l'algorithme
1, l'espace de demande, dont la taille est la somme de deux séquences déjà triées, est utilisé pour stocker les séquences fusionnées
2°, définissez deux pointeurs, dont la position initiale est celle de deux séquences déjà classées
3, comparer les éléments pointés par les deux pointeurs, choisir un élément relativement petit, le placer dans l'espace de fusion et déplacer le pointeur vers la position suivante
4, répétez l'étape 3 jusqu'à ce qu'un des pointeurs atteigne la fin de la séquence
5, copier tous les éléments restants de l'autre séquence directement à la fin de la séquence combinée
L'algorithme de recherche bipartite est un algorithme de recherche d'un élément spécifique dans une matrice ordonnée. Le processus de recherche commence à partir de l'élément intermédiaire de l' matrice et se termine si l'élément intermédiaire est exactement celui à rechercher. Si un élément spécifique est supérieur ou inférieur à l'élément intermédiaire, il est recherché dans la moitié de l' matrice qui est supérieure ou inférieure à l'élément intermédiaire et est comparé à partir de l'élément intermédiaire comme au début.
L'algorithme BFPRT résout les problèmes classiques de sélection de l'élément k plus grand (k plus petit) d'une séquence de n éléments et, grâce à une analyse habile, BFPRT garantit une complexité linéaire dans le pire des cas. L'idée de l'algorithme est similaire à celle de l'ordre rapide.
Les étapes de l'algorithme
1, en divisant les n éléments en groupes de 5 pour n/5 (en haut de la ligne) ;
2, extraire la médiane de chaque groupe, méthode de tri arbitraire, par exemple insérer le tri.
3, l'algorithme de sélection de l'appel récurrent trouve la médiane de tous les médians de l'étape précédente, et est défini comme x, en choisissant le plus petit médian dans le cas d'un nombre pair de médians.
4, pour diviser l'arithmétique par x, le nombre d'éléments inférieurs à x est égal à k et le nombre d'éléments supérieurs à x est égal à n - k.
5, si i==k, retourne x; si i
Condition d'arrêt: lorsque n = 1, l'élément i est retourné.
L'algorithme de recherche de priorité profonde (Depth-First-Search) est un type d'algorithme de recherche qui parcourt les nœuds de l'arbre le long de la profondeur de l'arbre, les branches de l'arbre de recherche le plus profondément possible. Lorsque tous les côtés du nœud v ont été explorés, la recherche revient au nœud de départ du côté du nœud v trouvé. Ce processus continue jusqu'à ce que tous les nœuds trouvés soient accessibles depuis le nœud source.
La recherche prioritaire approfondie est un algorithme classique de la cartographie qui permet de générer des tables de topologie correspondantes pour les cartes cibles. L'utilisation de tables de topologie permet de résoudre facilement de nombreux problèmes de cartographie connexes, tels que le problème du chemin le plus long, etc.
Les étapes de l'algorithme sont décrites en détail:
1° accéder au sommet v;
2, à partir des points adjacents non visités de v, la carte est parcourue en profondeur prioritaire; jusqu'à ce que les sommets du diagramme où le chemin est partagé avec v soient visités;
Si des sommets sont encore inaccessibles dans le graphique, recommencez à partir d'un sommet inaccessible et effectuez une exploration en profondeur prioritaire jusqu'à ce que tous les sommets du graphique aient été visités.
Les descriptions ci-dessus peuvent être plus abstraites, comme par exemple:
DFS part de v, après avoir commencé par un sommet v dans un des diagrammes d'accès, pour accéder à n'importe quel sommet voisin de celui-ci, w1; puis part de w1, pour accéder au sommet voisin de w1 mais non encore visité, w2; puis part de w2, pour effectuer une visite similaire,... et ainsi de suite, jusqu'à ce qu'il atteigne le sommet u où tous les sommets voisins ont été visités.
Ensuite, revenir en arrière et revenir au sommet que vous avez visité la dernière fois pour voir s'il y a d'autres sommets adjacents qui n'ont pas été visités. Si oui, visitez ce sommet, puis partez de ce sommet pour effectuer une visite similaire à celle précédente. Si non, retournez à l'étape précédente et effectuez une recherche.
L'algorithme de recherche par largeur est un algorithme de recherche graphique. En termes simples, le BFS est un algorithme de recherche par largeur qui traverse l'arbre à la largeur de l'arbre en commençant par le nœud racine. Si tous les nœuds sont visités, l'algorithme est arrêté.
Les étapes de l'algorithme
1, le premier est de placer le nœud racine dans la file d'attente.
2° Retirez le premier nœud de la file d'attente et vérifiez s'il s'agit d'un objectif.
Si la cible est trouvée, la recherche est interrompue et les résultats sont renvoyés. Si ce n'est pas le cas, tous les sous-nœuds directs qui n'ont pas encore été vérifiés sont ajoutés à la file d'attente.
Si la file d'attente est vide, cela signifie que l'ensemble du graphique a été examiné et qu'aucune cible n'est recherchée.
4° Répétez l'étape 2°.
L'algorithme de Dijkstra a été proposé par l'informaticien néerlandais Ezher Dijkstra. L'algorithme de Dijkstra utilise une recherche prioritaire large pour résoudre le problème du chemin le plus court d'une source unique d'un diagramme directionnel non négatif, ce qui aboutit à un arbre de chemin le plus court.
L'entrée de l'algorithme est constituée d'un diagramme orienté pondéré G, ainsi que d'un sommet source S dans G. Nous utilisons V pour représenter le ensemble de tous les sommets de G. Chaque côté de l'algorithme est constitué d'un couple d'éléments ordonnés formés par les deux sommets. U, v indiquent qu'il y a un chemin reliant le sommet u à v. Nous utilisons E pour représenter le ensemble de tous les côtés de G. Le poids du côté est défini par la fonction de pondération w: E→[0,∞].
Ainsi, w (u, v) est le poids non négatif du sommet u au sommet v. Le poids du côté peut être imaginé comme la distance entre les deux sommets. Le poids du chemin entre les deux points est la somme des poids de tous les côtés du chemin. On sait qu'il y a des sommets s et t dans V.
Les étapes de l'algorithme
1, la valeur de la distance correspondant au sommet de T au moment initial où S = {V0}, T = {les autres sommets}
Si
2, choisissez un sommet de T dont la valeur de distance est la plus faible W et qui n'est pas dans S, et joignez S
3, modification de la valeur de la distance entre les sommets du reste de T: modification de la valeur de la distance entre les sommets de V0 et Vi en ajoutant W comme sommet du milieu
Répétez les étapes 2 et 3 jusqu'à ce que S contient tous les sommets, c'est-à-dire que W = Vi
La programmation dynamique est une méthode utilisée en mathématiques, en informatique et en économie pour résoudre des problèmes complexes en décomposant les problèmes originaux en sous-problèmes relativement simples. La programmation dynamique est souvent utilisée pour des problèmes qui ont des propriétés de superposition et de structure optimale, et la méthode de programmation dynamique prend souvent beaucoup moins de temps que les solutions simples.
L'idée de base derrière la planification dynamique est très simple. En général, pour résoudre un problème donné, nous devons résoudre ses différentes parties (les problèmes de sous-ensemble) et résoudre les problèmes de sous-assemblage pour résoudre le problème d'origine. Souvent, de nombreux problèmes sont très similaires, de sorte que la planification dynamique essaie de résoudre chaque sous-problème une seule fois, ce qui réduit le volume de calcul: une fois que la solution d'un problème donné a été calculée, elle est stockée en mémoire pour être vérifiée directement la prochaine fois que vous avez besoin de résoudre le même problème.
Le problème le plus classique de la planification dynamique est celui des sacs à dos.
Les étapes de l'algorithme
1, propriété de la structure optimale. Si la solution de la sous-problème contenue dans la solution optimale du problème est également optimale, nous disons que le problème a la propriété de la structure optimale (c'est-à-dire qu'il satisfait aux principes d'optimisation optimales).
La superposition des sous-problèmes se produit lorsque les problèmes sont résolus de haut en bas par un algorithme de récurrence. Les sous-problèmes ne sont pas toujours nouveaux à chaque fois qu'ils sont résolus et certains sont calculés plusieurs fois. L'algorithme de planification dynamique utilise cette superposition des sous-problèmes en calculant une seule fois chaque sous-problème et en conservant les résultats dans une table.
L'algorithme de classification de Bayes est un algorithme de classification de probabilité simple basé sur le théorème de Bayes. Le classification de Bayes est basée sur le raisonnement de probabilité, c'est-à-dire sur la façon d'accomplir des tâches de raisonnement et de décision dans des conditions où la présence de diverses conditions est incertaine et dont la seule probabilité est connue. Le raisonnement de probabilité correspond au raisonnement de certitude.
Les classifiants de Bayes simples reposent sur des modèles de probabilité naturels précis, ce qui permet d'obtenir de très bons résultats de classification dans des ensembles de échantillons où l'apprentissage est supervisé. Dans de nombreuses applications pratiques, les estimations de paramètres de Bayes simples sont effectuées en utilisant des estimations maximales de similitude, c'est-à-dire que les modèles de Bayes simples fonctionnent sans les probabilités de Bayes ou de tout modèle de Bayes.
Malgré ces idées simples et ces hypothèses trop simplifiées, les classifiants Bayesian simples peuvent fonctionner assez bien dans de nombreuses situations réelles complexes.