Dix algorithmes pratiques de base que les programmeurs doivent connaître et leurs explications

• ### Algorithme 1: un algorithme de sélection rapide

Le tri rapide est un type d’algorithme de tri développé par Tony Hall. Dans les conditions moyennes, le tri de n projets nécessite ∞ (nlogn) de comparaisons. Dans les pires conditions, il faut ∞ (n2) de comparaisons, mais ce n’est pas courant. En fait, le tri rapide est généralement nettement plus rapide que les autres algorithmes ∞ (nlogn), car son cycle interne ∞ (innerloop) peut être réalisé très efficacement sur la plupart des architectures.

Le tri rapide utilise la stratégie Divideandconquer pour diviser une liste en deux sous-listes.

Les étapes de l’algorithme

• 1, sélectionnez un élément de l’array, appelé pivot,

• 1. réorganisez l’arrêté en plaçant tous les éléments inférieurs à la valeur de référence devant la valeur de référence, et tous les éléments supérieurs à la valeur de référence derrière la valeur de référence (le même nombre peut aller de l’un ou de l’autre côté). Après la sortie de cette partition, la référence est au milieu de l’arrêté.

• 3, récursivement (recursive) les sous-ensembles inférieurs à la valeur de référence et supérieurs à la valeur de référence.

  Le cas le plus fondamental de la récursivité est que la taille de l’arrangement est de zéro ou un, c’est-à-dire qu’il a toujours été bien ordonné. Bien que toujours récursif, l’algorithme sort toujours, car à chaque iteration, il place au moins un élément à sa dernière position.

• ### Algorithme 2: algorithme de sélection par lots

Le Heapsort est une sorte d’algorithme de tri conçu pour exploiter la structure de données de la pile. La pile est une structure qui s’apparente à un arbre bissectrique parfait, tout en satisfaisant la propriété de la pile: la valeur de la clé ou de l’index d’un sous-nœud est toujours inférieure à (ou supérieure à) son nœud parent.

La complexité temporelle moyenne de la sélection de la pile est Ω ((nlogn) 。

Les étapes de l’algorithme

• 1, créer une pile H.[0..n-1]

• 2 - Interchangez le début (maximum) et la fin de la pile

• 3, réduire la taille de la pile à 1 et appeler shift_down ((0)), afin d’ajuster les données du haut de la nouvelle pile à la position correspondante

• 4, répétez l’étape 2 jusqu’à ce que la pile soit de taille 1

• Algorithme 3: Résumé et tri

Mergesort est un algorithme de sélection efficace basé sur l’opération de fusion. Il s’agit d’une application très typique de la méthode DivideandConquer.

Les étapes de l’algorithme

• 1. demande un espace de taille équivalente à la somme de deux séquences déjà triées et utilise cet espace pour stocker les séquences fusionnées

• 2/ définir deux pointeurs dont la position initiale correspond à la position initiale de deux séquences déjà triées

• 3 Comparer les éléments pointés par les deux pointeurs, sélectionner des éléments relativement petits à 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 pointeur atteigne la fin de la séquence

• 1. copier tous les éléments restants d’une autre séquence directement à la fin de la séquence de fusion

• Algorithme 4: algorithme de recherche par fractionnement

L’algorithme de recherche binaire est un algorithme de recherche d’un élément donné dans une matrice ordonnée. La recherche commence à partir de l’élément du milieu de l’array et se termine si l’élément du milieu est l’élément recherché; si un élément particulier est supérieur ou inférieur à l’élément du milieu, la recherche est effectuée dans la moitié de l’array supérieure ou inférieure à l’élément du milieu, et la comparaison commence à partir de l’élément du milieu comme au début.

• ### Algorithme cinq: BFPRT (algorithme de recherche linéaire)

L’algorithme BFPRT résout le problème classique de sélectionner le k plus grand (k plus petit) élément d’une séquence d’éléments n, et par une analyse astucieuse, il garantit une complexité en temps linéaire dans le pire des cas. L’idée de l’algorithme est similaire à celle du tri rapide, bien sûr, pour que l’algorithme atteigne une complexité en temps de o (n) dans le pire des cas, les cinq auteurs de l’algorithme ont fait un traitement subtil.

Les étapes de l’algorithme

• 1 , divisez n éléments par groupe de 5 en n/5 groupes.

• 2/ Prendre la médiane de chaque groupe, et sélectionner une méthode de sélection arbitraire, telle que l’insertion de sélection.

• 3, l’appel recursif de l’algorithme de sélection pour trouver la médiane de tous les moyennes de l’étape précédente, définie sur x, en choisissant la plus petite du milieu dans le cas d’un nombre pair de moyennes.

• 4 , divisez l’array en utilisant x. Soyez sûr que les nombres inférieurs ou égaux à x sont k, et les nombres supérieurs ou égaux à x sont n-k.

• 5 , si i==k, retourne x; si ik, recherche de manière récurrente l’élément inférieur à i-k parmi les éléments supérieurs à x.

  Condition de finition: lorsque n = 1, le retour est le sous-élément i.

• Algorithme 6: DFS (pour la recherche prioritaire en profondeur)

La recherche en profondeur-première (Depth-First-Search) est une sorte d’algorithme de recherche qui parcourt les nœuds de l’arbre à la profondeur de l’arbre et recherche les branches de l’arbre aussi profondes que 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é où le nœud v a été trouvé.

La recherche par priorité de profondeur est un algorithme classique de la cartographie. L’utilisation de l’algorithme de recherche par priorité de profondeur permet de générer une table de topographie correspondante de la carte cible. L’utilisation d’une table de topographie permet de résoudre facilement de nombreux problèmes de cartographie connexes, tels que le problème du chemin le plus grand, etc.

Les étapes de l’algorithme sont décrites en détail:

• 1° accéder au sommet v;

• 2/ La carte est parcourue en profondeur en priorité, en partant des points voisins non visités de la carte, jusqu’à ce que tous les sommets de la carte ayant un chemin commun avec la carte soient visités;

• 1. Si un sommet n’a pas encore été visité, recommencer à partir d’un sommet non visité et recommencer la traversée en profondeur jusqu’à ce que tous les sommets du graphique aient été visités.

  La description ci-dessus est peut-être un peu abstraite, mais voici un exemple:

  DFS commence par un sommet v dans le diagramme d’accès, puis part de v pour accéder à n’importe quel sommet voisin de celui-ci w1; puis part de w1 pour accéder à un sommet voisin de w1 mais pas encore visité w2; puis part de w2 pour une visite similaire, et ainsi de suite jusqu’à ce que tous les sommets voisins aient été visités.

  Ensuite, faites un pas en arrière et retournez au sommet que vous venez de visiter la dernière fois pour voir s’il y a d’autres sommets adjacents qui n’ont pas été visités. Si c’est le cas, accédez à ce sommet, puis partez de ce sommet pour effectuer une visite similaire à la précédente. Si ce n’est pas le cas, faites un pas en arrière pour effectuer une recherche.

• Algorithme 7: BFS (Bandwidth Prioritized Search) (Algorithme 7: BFS (Bandwidth Prioritized Search) est une méthode de recherche utilisée dans le domaine de la recherche.

BFS est un type d’algorithme de recherche graphique. En termes simples, BFS est un algorithme de recherche graphique qui commence par un nœud racine et parcourt l’arbre à travers la largeur de l’arbre.

Les étapes de l’algorithme

• 1 - D’abord, placez le nœud racine dans la queue.

• 1. Prenez le premier nœud de la queue et vérifiez s’il est la cible.

  Si le but est atteint, la recherche est terminée et les résultats rapportés. Sinon, ajoutez tous les sous-nœuds directs qui n’ont pas encore été vérifiés à la queue.

• 3 Si la file d’attente est vide, cela signifie que la carte entière a été vérifiée, c’est-à-dire qu’il n’y a pas d’objet à rechercher dans la carte.

• 4 Répétez l’étape 2.

• Algorithme huit: l’algorithme de Dijkstra, qui est utilisé pour calculer le nombre d’étoiles.

L’algorithme de Dijkstra (en néerlandais: Dijkstra-salgorithme) est un algorithme de recherche par priorité d’amplitude qui permet de résoudre le problème du plus court chemin d’une seule source de diagramme orienté non négatif. L’algorithme est souvent utilisé pour des algorithmes de routage ou comme un sous-module d’autres algorithmes de diagramme.

L’entrée de l’algorithme contient un graphe vectoriel G avec une pondération et un sommet de source S dans G. On utilise V pour représenter l’ensemble de tous les sommets de G. Les côtés de chaque graphe sont des paires d’éléments ordonnés formés par les deux sommets.[0,∞] définition

Ainsi, w{\displaystyle u,v} est le poids non négatif ({\displaystyle {n} ,{\displaystyle {n} ,{\displaystyle {n} ,{\displaystyle {n} ,{\displaystyle {n} ,{\displaystyle {n} ,{\displaystyle {n} ,{\displaystyle {n} ,{\displaystyle {n} ,{\displaystyle {n} ,{\displaystyle {n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,{n} ,

Les étapes de l’algorithme

• 1, la valeur de la distance correspondant au sommet dans T, au moment de départ S = {V0}, T = {autres sommets} Si ,d{V0,Vi) est une valeur de poids sur l’arc Si n’existe pas, d (V0,Vi) est égal à ∞

• 1. Prenez un sommet W de T dont la distance est la plus petite et qui n’est pas dans S, et ajoutez S

• Modifier la distance entre les sommets des autres points de T: ajouter W comme sommet intermédiaire et raccourcir la distance entre V0 et Vi.

  Répétez les étapes 2 et 3 ci-dessus jusqu’à ce que tous les sommets soient inclus dans S, à savoir W = Vi

• Algorithme 9: Algorithme de programmation dynamique

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 s’applique souvent à des problèmes avec des sous-problèmes superposés et des propriétés de structure optimale, et les méthodes de programmation dynamique prennent souvent beaucoup moins de temps que les solutions simples.

L’idée de base de la planification dynamique est très simple: en général, pour résoudre un problème donné, nous devons résoudre les différentes parties de celui-ci (les problèmes de sous-groupes), puis combiner les solutions des problèmes de sous-groupes pour obtenir la solution du problème de base. Habituellement, de nombreux problèmes de sous-groupes sont très similaires, pour cela, la méthode de planification dynamique essaie de résoudre chaque problème de sous-groupe une seule fois, réduisant ainsi le nombre de calculs: une fois que la solution d’un problème de sous-groupe donné a été calculée, elle est stockée dans la mémoire, afin de pouvoir l’afficher directement la prochaine fois qu’il est nécessaire de résoudre le même problème de sous-groupe. Cette pratique est particulièrement utile lorsque le nombre de problèmes de sous-groupe répétés augmente par rapport à l’entrée de l’indice de taille.

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 optimale d’un problème contient une solution optimale à un sous-problème, nous disons que le problème a une propriété de la structure optimale (c’est-à-dire qu’il satisfait au principe d’optimisation). La propriété de la structure optimale fournit un indice important pour la résolution du problème par un algorithme de planification dynamique .

2 La superposition des sous-problèmes La superposition des sous-problèmes signifie que chaque sous-problème n’est pas toujours un nouveau problème lorsqu’il est résolu de haut en bas avec un algorithme récurrent. Certains sous-problèmes sont calculés plusieurs fois. L’algorithme de planification dynamique utilise cette superposition des sous-problèmes, qui ne calcule qu’une seule fois pour chaque sous-problème, puis conserve ses résultats dans un tableau.

• ### Algorithme 10: classification naïve par Bayes

Les algorithmes simplistes de classification bayésienne sont des algorithmes de classification de probabilité simples, basés sur les théorèmes de Bayes. La classification bayésienne est basée sur la déduction de probabilité, qui consiste à déterminer comment effectuer des tâches de raisonnement et de décision lorsque diverses conditions sont incertaines et que seules les probabilités sont connues.

Le classificateur simple Bayesian s’appuie sur des modèles de probabilité naturelle précis, qui permettent d’obtenir de très bons résultats de classification dans des concentrations d’échantillons d’apprentissage supervisé. Dans de nombreuses applications pratiques, les paramètres du modèle simple Bayesian sont estimés à l’aide de la méthode d’estimation de la plus grande similitude, c’est-à-dire que le modèle simple Bayesian ne fonctionne pas avec une probabilité Bayesian ou un modèle Bayesian.

Malgré ces idées simplistes et ces hypothèses simplistes, le classificateur Bayesian simpliste est capable d’obtenir de très bons résultats dans de nombreux cas de réalité complexes.