Qu’est-ce qu’un algorithme ?

Un algorithme est une procédure étape par étape pour résoudre un problème. Un bon algorithme doit être optimisé en termes de temps et d’espace. Différents types de problèmes nécessitent différents types de techniques algorithmiques pour être résolus de la manière la plus optimisée possible. Il existe de nombreux types d'algorithmes, mais les algorithmes les plus importants et fondamentaux dont vous avez besoin sont abordés dans cet article.

1. Algorithme de force brute :

Il s’agit du type d’algorithme le plus basique et le plus simple. Un algorithme de force brute est l'approche simple d'un problème, c'est-à-dire la première approche qui nous vient à l'esprit lorsque nous voyons le problème. Plus techniquement, cela revient à répéter toutes les possibilités disponibles pour résoudre ce problème.

Exemple:

S'il y a un verrou avec un code PIN à 4 chiffres. Les chiffres doivent être choisis entre 0 et 9, puis la force brute essaiera toutes les combinaisons possibles une par une comme 0001, 0002, 0003, 0004, et ainsi de suite jusqu'à ce que nous obtenions le bon code PIN. Dans le pire des cas, il faudra 10 000 essais pour trouver la bonne combinaison.

méthode égale en java

2. Algorithme récursif :

Ce type d'algorithme est basé sur récursivité . En récursion, un problème est résolu en le divisant en sous-problèmes du même type et en s'appelant encore et encore jusqu'à ce que le problème soit résolu à l'aide d'une condition de base.
Certains problèmes courants résolus à l’aide d’algorithmes récursifs sont Factorielle d'un nombre , Série Fibonacci , La tour de Hanoi , DFS pour graphique , etc.

un) Algorithme Diviser pour régner :

Dans les algorithmes Divide and Conquer, l’idée est de résoudre le problème en deux sections, la première section divise le problème en sous-problèmes du même type. La deuxième section consiste à résoudre le problème le plus petit de manière indépendante, puis à additionner le résultat combiné pour produire la réponse finale au problème.
Certains problèmes courants résolus à l’aide des algorithmes Divide and Conquers sont Recherche binaire , Tri par fusion , Tri rapide, Multiplication matricielle de Strassen , etc.

b) Algorithmes de programmation dynamique :

Ce type d'algorithme est également connu sous le nom de technique de mémorisation car en cela l'idée est de stocker le résultat précédemment calculé pour éviter de le calculer encore et encore. En programmation dynamique, divisez le problème complexe en plus petits sous-problèmes qui se chevauchent et stockez le résultat pour une utilisation future.
Les problèmes suivants peuvent être résolus à l'aide de l'algorithme de programmation dynamique Problème de sac à dos , Planification pondérée des tâches , Algorithme Floyd Warshall , etc.

c) Algorithme gourmand :

Dans l’algorithme gourmand, la solution est construite partie par partie. La décision de choisir la partie suivante est prise sur la base du fait qu'elle apporte un bénéfice immédiat. Il ne considère jamais les choix qui ont été faits précédemment.
Certains problèmes courants qui peuvent être résolus grâce à l'algorithme gourmand sont Algorithme de chemin le plus court de Dijkstra , L'algorithme de Prim , L'algorithme de Kruskal , Codage de Huffman , etc.

d) Algorithme de retour en arrière :

Dans l'algorithme de retour en arrière, le problème est résolu de manière incrémentale, c'est-à-dire qu'il s'agit d'une technique algorithmique permettant de résoudre des problèmes de manière récursive en essayant de construire une solution de manière incrémentielle, une pièce à la fois, en supprimant les solutions qui ne parviennent pas à satisfaire les contraintes du problème. point de temps.
Certains problèmes courants qui peuvent être résolus grâce à l'algorithme de retour en arrière sont les suivants : Cycle hamiltonien , Problème de coloration M , N Reine Problème , Problème de rat dans le labyrinthe , etc.

3. Algorithme randomisé :

Dans l'algorithme randomisé, nous utilisons un nombre aléatoire. Cela aide à décider du résultat attendu. La décision de choisir le nombre aléatoire afin qu'il donne un avantage immédiat
Certains problèmes courants qui peuvent être résolus grâce à l'algorithme randomisé sont le tri rapide : dans le tri rapide, nous utilisons le nombre aléatoire pour sélectionner le pivot.

4. Algorithme de tri :

L'algorithme de tri est utilisé pour trier les données par ordre croissant ou décroissant. Il est également utilisé pour organiser les données de manière efficace et utile.
Certains problèmes courants qui peuvent être résolus grâce à l'algorithme de tri sont le tri à bulles, le tri par insertion, le tri par fusion, le tri par sélection et le tri rapide sont des exemples de l'algorithme de tri.

5. Algorithme de recherche :

L'algorithme de recherche est l'algorithme utilisé pour rechercher la clé spécifique en particulier les données triées ou non triées. Certains problèmes courants qui peuvent être résolus grâce à l'algorithme de recherche sont la recherche binaire ou la recherche linéaire qui est un exemple d'algorithme de recherche.

6. Algorithme de hachage :

Les algorithmes de hachage fonctionnent de la même manière que l'algorithme de recherche, mais ils contiennent un index avec un ID de clé, c'est-à-dire une paire clé-valeur. Lors du hachage, nous attribuons une clé à des données spécifiques.
Certains problèmes courants peuvent être résolus grâce à l’algorithme de hachage lors de la vérification du mot de passe.