Structures de données et algorithmes (DSA) faire référence à l'étude des méthodes d'organisation et de stockage des données et à la conception de procédures (algorithmes) pour résoudre des problèmes, qui opèrent sur ces structures de données. DSA est l’une des compétences les plus importantes que tout étudiant en informatique doit posséder. On constate souvent que les personnes ayant une bonne connaissance de ces technologies sont de meilleurs programmeurs que les autres et craquent ainsi dans les interviews de presque tous les géants de la technologie. Ce Tutoriel DSA vise à vous aider à apprendre les structures de données et les algorithmes (DSA) rapidement et facilement.

Table des matières

• Formulaire complet DSA
• Qu’est-ce que le DSA ?
• Comment apprendre le DSA ?
• Chaîne
• Listes liées
• Matrice/Grille
• Empiler
• File d'attente
• Tas
• Hacher
• Arbre
• Graphique

• Algorithme de recherche
• Algorithme de tri
• Algorithme Diviser pour régner
• Algorithmes gourmands
• Récursivité
• Algorithme de retour en arrière
• Programmation dynamique
• Algorithmes graphiques :
• Recherche de modèles
• Algorithmes mathématiques
• Algorithmes géométriques
• Algorithmes au niveau du bit
• Algorithmes randomisés
• Algorithme de branchement et de liaison

Formulaire complet DSA

Le terme DSA signifie Structures de données et algorithmes , dans le contexte de l'informatique.

Qu’est-ce que le DSA ?

Structures de données et algorithmes (DSA) faire référence à l'étude des méthodes d'organisation et de stockage des données et à la conception de procédures (algorithmes) pour résoudre des problèmes, qui opèrent sur ces structures de données.

Comment apprendre le DSA ?

La première chose à faire est de diviser l’ensemble de la procédure en petites parties qui doivent être effectuées séquentiellement. Le processus complet pour apprendre DSA à partir de zéro peut être divisé en 5 parties :

1. Apprenez au moins un langage de programmation (nous laissons cela à votre choix.)
2. Apprendre les structures de données
3. Apprendre les algorithmes
4. Découvrez les complexités du temps et de l’espace
5. Problèmes pratiques sur DSA

Comment apprendre le DSA ?

En espérant que vous avez appris un langage de programmation de votre choix, passons à l'étape suivante pour apprendre DSA dans ce didacticiel DSA.

Voici l’étape la plus importante et la plus attendue de la feuille de route pour l’apprentissage de la structure des données et des algorithmes : l’étape où vous commencez à vous renseigner sur DSA. Le sujet du DSA se compose de deux parties :

• Structures de données
• Algorithmes

Bien qu’il s’agisse de deux choses différentes, elles sont étroitement liées et il est très important de suivre la bonne voie pour les apprendre le plus efficacement possible. Si vous ne savez pas lequel apprendre en premier, nous vous recommandons de consulter notre analyse détaillée sur le sujet : Ici, nous avons suivi le flux d'apprentissage d'une structure de données, puis les algorithmes les plus liés et les plus importants utilisés par cette structure de données.

Apprendre les structures de données

Structures de données sont des composants essentiels qui aident à organiser et à stocker efficacement les données dans la mémoire de l'ordinateur. Ils offrent un moyen de gérer et de manipuler efficacement les données, permettant des opérations d'accès, d'insertion et de suppression plus rapides. Les structures de données courantes incluent tableaux, listes chaînées, piles, files d'attente, arbres et graphiques , chacun servant des objectifs spécifiques en fonction des exigences du problème à résoudre. Comprendre les structures de données est fondamental pour concevoir des algorithmes efficaces et optimiser les performances des logiciels.

Tableau est une structure de données linéaire qui stocke une collection d'éléments du même type de données. Les éléments se voient attribuer une mémoire contiguë, permettant un accès en temps constant. Chaque élément possède un numéro d'index unique.

• Opérations sur le tableau :
  • Traversée : Itération à travers les éléments d’un tableau.
  • Insertion : Ajout d'un élément au tableau à un index spécifique.
  • Effacement : Suppression d'un élément du tableau à un index spécifique.
  • Recherche : Recherche d'un élément dans le tableau par sa valeur ou son index.
• Types de tableaux :
  • Tableau unidimensionnel : Un tableau simple avec une seule dimension.
  • Tableau multidimensionnel : Un tableau à plusieurs dimensions, tel qu'une matrice.
• Applications du tableau :
  • Stockage des données de manière séquentielle
  • Implémentation de files d'attente, de piles et d'autres structures de données
  • Représenter des matrices et des tableaux
• Sujets connexes sur Array :
  • Tutoriel sur les tableaux
  • Top 50 des problèmes de codage de tableau pour les entretiens
  • Problèmes de pratique sur les tableaux

2. Chaîne

UN chaîne est une séquence de caractères, généralement utilisée pour représenter du texte. Il est considéré comme un type de données permettant la manipulation et le traitement de données textuelles dans des programmes informatiques.

• Opérations sur une chaîne :
  • Enchaînement : Joindre deux cordes ensemble.
  • Comparaison : Comparaison lexicographique de deux chaînes.
  • Sous-chaîne extraction : Extraire une sous-chaîne d'une chaîne.
  • Recherche : Recherche d'une sous-chaîne dans une chaîne.
  • Modification : Modification ou remplacement de caractères dans une chaîne.
• Applications de la chaîne :
  • Traitement de texte
  • Correspondance de motifs
  • La validation des données
  • Gestion de base de données
• Articles Similaires:
  • Tutoriel sur les chaînes
  • Top 50 des problèmes de codage de chaînes pour les entretiens
  • Problèmes de pratique sur la chaîne

3. Listes liées

UN liste chaînée est une structure de données linéaire qui stocke les données dans des nœuds reliés par des pointeurs. Contrairement aux tableaux, les listes chaînées ne sont pas stockées dans des emplacements mémoire contigus.

• Caractéristiques de la liste chaînée :
  • Dynamique : Les listes chaînées peuvent être facilement redimensionnées en ajoutant ou en supprimant des nœuds.
  • Non contigu : Les nœuds sont stockés dans des emplacements de mémoire aléatoires et connectés par des pointeurs.
  • Accès séquentiel : Les nœuds ne sont accessibles que de manière séquentielle, en commençant par la tête de liste.
• Opérations sur la liste chaînée :
  • Création : Création d'une nouvelle liste chaînée ou ajout d'un nouveau nœud à une liste existante.
  • Traversée : Parcourir la liste et accéder à chaque nœud.
  • Insertion : Ajout d'un nouveau nœud à une position spécifique dans la liste.
  • Effacement : Suppression d'un nœud de la liste.
  • Recherche : Recherche d'un nœud avec une valeur spécifique dans la liste.
• Types de liste chaînée :
  • Liste à chaînage unique : Chaque nœud pointe vers le nœud suivant dans la liste.
  • Liste doublement liée : Chaque nœud pointe à la fois vers les nœuds suivant et précédent dans la liste.
  • Liste chaînée circulaire : Le dernier nœud renvoie au premier nœud, formant une boucle circulaire.
• Applications de la liste chaînée :
  • Les listes chaînées sont utilisées dans diverses applications, notamment :
  • Implémentation de files d'attente et de piles
  • Représenter des graphiques et des arbres
  • Gestion des données ordonnées
  • Gestion de la mémoire
• Rubriques connexes:
  • Tutoriel sur les listes liées
  • Top 50 des problèmes sur la liste chaînée pour les entretiens
  • Problèmes de pratique sur les listes liées

4. Matrice/Grille

UN matrice est un tableau bidimensionnel d’éléments, disposés en lignes et en colonnes. Il est représenté sous la forme d’une grille rectangulaire, chaque élément étant à l’intersection d’une ligne et d’une colonne.

• Concepts clés:
  • Lignes : Lignes horizontales d'éléments dans une matrice.
  • Colonnes : Lignes verticales d'éléments dans une matrice.
  • Dimensions : Le nombre de lignes et de colonnes dans une matrice (par exemple, une matrice 3×4 a 3 lignes et 4 colonnes).
  • Élément Accéder : Les éléments sont accessibles à l'aide d'index de ligne et de colonne (par exemple, M[2][3] fait référence à l'élément de la ligne 2, colonne 3).
• Applications de Matrice/Grille :
  • Traitement d'image
  • L'analyse des données
  • Problèmes d'optimisation
• Articles Similaires:
  • Tutoriel Matrice/Grille
  • Top 50 des problèmes sur la matrice/grille pour les entretiens
  • Problèmes de pratique sur la matrice/la grille

5. Empiler

Empiler est une structure de données linéaire qui suit un ordre particulier dans lequel les opérations sont effectuées. La commande peut être LIFO (dernier entré, premier sorti) ou FILO (premier entré, dernier sorti) . LIFO implique que l'élément inséré en dernier ressort en premier et RANGÉE implique que l’élément inséré en premier sort en dernier.

• Opération sur pile :
  • Pousser : Ajoute un élément en haut de la pile
  • Populaire : Supprime et renvoie l'élément en haut de la pile
  • Coup d'oeil : Renvoie l'élément en haut de la pile sans le supprimer
  • Taille : Renvoie le nombre d'éléments dans la pile
  • Est vide : Vérifie si la pile est vide
• Applications de la pile :
  • Appels de fonction
  • Évaluation des expressions
  • Retour en arrière
  • Opérations Annuler/Rétablir
• Sujets connexes sur Stack :
  • Tutoriel de pile
  • Top 50 des problèmes sur la pile pour les entretiens
  • Problèmes de pratique sur Stack

6. File d'attente

UN File d'attente La structure des données est un concept fondamental en informatique utilisé pour stocker et gérer les données dans un ordre spécifique. Il suit le principe de Premier entré, premier sorti ( FIFO ), où le premier élément ajouté à la file d'attente est le premier à être supprimé

• Opération sur la file d'attente :
  • Mettre en file d'attente : Ajoute un élément à l'arrière de la file d'attente
  • Par conséquent : Supprime un élément du début de la file d'attente
  • Coup d'oeil : Récupère l'élément avant sans le supprimer
  • Est vide : Vérifie si la file d'attente est vide
  • Est rempli : Vérifie si la file d'attente est pleine
• Type de file d'attente :
  • File d'attente circulaire : Le dernier élément se connecte au premier élément
  • File d'attente à double extrémité (Deque) : Les opérations peuvent être effectuées des deux côtés
  • File d'attente de priorité : Les éléments sont classés en fonction de la priorité
• Applications de la file d'attente :
  • Planification des travaux
  • File d'attente des messages
  • Modélisation par simulation
  • Mise en mémoire tampon des données
• Rubriques connexes:
  • Tutoriel de file d'attente
  • Top 50 des problèmes en attente pour les entretiens
  • Problèmes de pratique sur la file d'attente

7. Tas

UN Tas est une structure de données arborescente binaire complète qui satisfait la propriété tas : pour chaque nœud, la valeur de ses enfants est inférieure ou égale à sa propre valeur. Les tas sont généralement utilisés pour implémenter files d'attente prioritaires , où le plus petit (ou le plus grand) élément est toujours à la racine de l'arbre.

• Opérations de tas :
  • Insérer : Ajoute un nouvel élément au tas tout en conservant les propriétés du tas.
  • Extraire-Max/Extraire-Min : Supprime l'élément racine et restructure le tas.
  • Touche d'augmentation/diminution : Met à jour la valeur d'un nœud et restructure le tas.
• Types de tas :
  • Tas maximum : Le nœud racine a la valeur maximale parmi ses enfants.
  • Min-Tas : Le nœud racine a la valeur minimale parmi ses enfants.
• Applications du tas :
  • Files d'attente prioritaires
  • Tri
  • Algorithmes graphiques (par exemple, l'algorithme de Dijkstra)
• Articles Similaires:
  • Tutoriel sur le tas
  • Top 50 des problèmes sur le tas pour les entretiens
  • Problèmes de pratique sur le tas

8. Hacher

Hachage est une technique qui génère une sortie de taille fixe (valeur de hachage) à partir d'une entrée de taille variable à l'aide de formules mathématiques appelées fonctions de hachage . Le hachage est utilisé pour déterminer un index ou un emplacement pour stocker un élément dans une structure de données, permettant une récupération et une insertion efficaces.

• Concepts clés:
  • Fonction de hachage : Une fonction mathématique qui mappe une entrée à une valeur de hachage.
  • Table de hachage : Une structure de données qui stocke des paires clé-valeur, où la clé est une valeur de hachage et la valeur est les données réelles.
  • Collision : Lorsque deux clés différentes produisent la même valeur de hachage.
• Types de fonctions de hachage :
  • Méthode de division : divise l'entrée par une constante et utilise le reste comme valeur de hachage.
  • Milieu carré Méthode : met au carré l'entrée et prend les chiffres du milieu comme valeur de hachage.
  • Méthode de pliage : divise l'entrée en blocs de taille égale et les additionne pour obtenir la valeur de hachage.
  • Méthode de multiplication : Multiplie l'entrée par une constante et prend la partie fractionnaire comme valeur de hachage.

• Techniques de résolution des collisions :
  • Chaînage séparé (hachage ouvert) : stocke les éléments en collision dans une liste chaînée à la valeur de hachage correspondante.
  • Adressage ouvert (hachage fermé) : utilise diverses stratégies pour trouver un emplacement alternatif pour les éléments en collision dans la table de hachage.
• Applications du hachage :
  • Stocker et récupérer efficacement des données dans des bases de données et des systèmes de fichiers.
  • Vérification des mots de passe et des signatures numériques.
  • Distribution des requêtes sur plusieurs serveurs.
  • Génération de hachages sécurisés pour l'intégrité des données et l'authentification.
• Articles Similaires:
  • Tutoriel de hachage
  • Problèmes de pratique sur le hachage

9. Arbre

UN arbre est une structure de données hiérarchique non linéaire composée de nœuds connectés par des arêtes, avec un nœud supérieur appelé racine et des nœuds ayant des nœuds enfants. Il est utilisé en informatique pour organiser efficacement les données.

qu'est-ce que SVN Checkout

• Traversée de l'arbre : Les méthodes de traversée d'arbre sont utilisées pour visiter et traiter des nœuds dans une structure de données arborescente. Les trois méthodes de parcours courantes sont :
  • En ordre : Visitez le sous-arbre gauche, le nœud actuel, puis le sous-arbre droit.
  • Pré-commander : Visitez le nœud actuel, le sous-arbre gauche, puis le sous-arbre droit.
  • Post-commande : Visitez le sous-arbre gauche, le sous-arbre droit, puis le nœud actuel.
• Classifications des arbres :
  • Classements de Des arbres faire référence au regroupement des arbres en fonction de certaines caractéristiques ou critères. Cela peut impliquer de catégoriser les arbres en fonction de leur facteur d'équilibre, du degré de nœuds, des propriétés d'ordre, etc. Vous trouverez ci-dessous quelques classifications importantes des arbres.

• Applications des arbres :
  • Systèmes de fichiers
  • Bases de données
  • Documents XML
  • Intelligence artificielle
• Articles Similaires:
  • Tutoriel sur les arbres
  • Top 50 des problèmes de codage d'arborescence
  • Pratiquez des problèmes sur Tree

10. Graphique

UN Graphique est une structure de données non linéaire constituée d'un ensemble fini de sommets (ou nœuds) et d'un ensemble d'arêtes qui relient une paire de nœuds.

• Traversées du graphique :
  • Recherche en largeur d'abord (BFS) : Visite les nœuds niveau par niveau.
  • Recherche en profondeur d'abord (DFS) : visite les nœuds de manière récursive, en explorant une branche à la fois.
• Applications des graphiques :
  • Réseaux sociaux
  • Cartes et navigation
  • Planification
  • Exploration de données
• Articles Similaires:
  • Représentation graphique
  • Types de graphiques
  • Tutoriel graphique
  • Problèmes pratiques sur Graph

Apprendre les algorithmes

Une fois que vous avez dégagé les concepts de Structures de données , il est maintenant temps de commencer votre voyage à travers le Algorithmes . En fonction du type de nature et d'utilisation, les algorithmes sont regroupés en plusieurs catégories, comme indiqué ci-dessous :

1. Algorithme de recherche

Algorithmes de recherche sont utilisés pour localiser des données spécifiques dans un ensemble de données plus large. Cela permet de trouver la présence d’une valeur cible dans les données. Il existe différents types d’algorithmes de recherche, chacun ayant sa propre approche et sa propre efficacité.

• Algorithmes de recherche les plus courants :
  • Recherche linéaire : Recherche itérative d'un bout à l'autre.
  • Recherche binaire : Recherche diviser pour régner sur un tableau trié, réduisant de moitié l'espace de recherche à chaque itération.
  • Recherche ternaire : Recherche diviser pour régner sur un tableau trié, divisant l'espace de recherche en trois parties à chaque itération.
• Autres algorithmes de recherche :
  • Recherche sautée
  • Recherche par interpolation
  • Recherche exponentielle
• Rubriques connexes:
  • Problèmes pratiques sur l'algorithme de recherche

2. Algorithme de tri

Algorithmes de tri sont habitués à organiser les éléments d’une liste dans un ordre spécifique, tel que numérique ou alphabétique. Il organise les éléments de manière systématique, facilitant ainsi la recherche et l'accès à des éléments spécifiques.

Il existe de nombreux types d’algorithmes de tri différents. Certains algorithmes largement utilisés sont :

Rubriques connexes:

• Tutoriel sur l'algorithme de tri
• Principales questions et problèmes d'entretien de tri
• Problèmes pratiques sur l'algorithme de tri

3. Algorithme diviser pour mieux régner

Diviser et conquérir les algorithmes suivent une stratégie récursive pour résoudre les problèmes en les divisant en sous-problèmes plus petits, en résolvant ces sous-problèmes et en combinant les solutions pour obtenir la solution finale.

Pas:

1. Diviser : Divisez le problème en sous-problèmes plus petits et indépendants.
2. Conquérir : Résolvez de manière récursive chaque sous-problème.
3. Combiner : Fusionner les solutions des sous-problèmes pour obtenir la solution finale.

Exemples:

• Tri par fusion : divise le tableau en deux moitiés, trie chaque moitié de manière récursive et fusionne les moitiés triées.
• Tri rapide : sélectionne un élément pivot, divise le tableau en deux sous-tableaux en fonction du pivot et trie de manière récursive chaque sous-tableau.
• Recherche binaire : divise l'espace de recherche en deux à plusieurs reprises jusqu'à ce que l'élément cible soit trouvé ou que l'espace de recherche soit épuisé.

Articles Liés:

• Didacticiel Diviser pour mieux régner
• Pratiquez des problèmes sur l'algorithme Divide And Conquer

4. Algorithmes gourmands

Comme son nom l'indique, cet algorithme construit la solution une pièce à la fois et choisit la pièce suivante qui donne l'avantage le plus évident et le plus immédiat, c'est-à-dire qui est le choix le plus optimal à ce moment-là. Ainsi, les problèmes pour lesquels le choix localement optimal conduit également aux solutions globales conviennent le mieux à Greedy.

Certains problèmes importants des algorithmes gourmands sont :

Articles Liés:

• Tutoriel sur l'algorithme gourmand
• Problèmes de pratique sur l'algorithme Greedy

5. Récursion

Récursivité est une technique de programmation où une fonction s'appelle selon sa propre définition. Il est généralement utilisé pour résoudre des problèmes qui peuvent être décomposés en instances plus petites du même problème. Par exemple: Tours de Hanoï (TOH) , Calcul factoriel et Séquence de Fibonacci etc.

survoler en CSS

Pas :

• Cas de base : Définissez une condition qui arrête les appels récursifs et fournit une solution.
• Cas récursif : Définissez les étapes pour décomposer le problème en instances plus petites et effectuer des appels récursifs.
• Retour : Renvoyez la solution des appels récursifs et combinez-les pour résoudre le problème d'origine.

Ce qui fait de Recursion l'un des algorithmes les plus utilisés, c'est qu'il constitue la base de nombreux autres algorithmes tels que Traversées d'arbres , Parcours de graphiques , Algorithmes Diviser et conquérir et Algorithmes de retour en arrière .

Rubriques connexes:

• Tutoriel de récursivité
• Fonctions récursives
• Récursion de la queue
• Top 50 des problèmes liés à l'algorithme de récursion pour les entretiens
• Problèmes pratiques sur l'algorithme de récursion

6. Algorithme de retour en arrière

Comme mentionné précédemment, le Retour en arrière L'algorithme est dérivé de l'algorithme de récursion, avec la possibilité de revenir en arrière si une solution récursive échoue, c'est-à-dire qu'en cas d'échec d'une solution, le programme remonte au moment où elle a échoué et s'appuie sur une autre solution. En gros, il essaie toutes les solutions possibles et trouve la bonne.

Certains problèmes importants et les plus courants des algorithmes de backtracking, que vous devez résoudre avant d’aller de l’avant, sont :

Article associé:

• Tutoriel de retour en arrière
• Problèmes pratiques sur l'algorithme de backtracking

7. Programmation dynamique

Programmation dynamique est une méthode utilisée en mathématiques et en informatique pour résoudre des problèmes complexes en les décomposant en sous-problèmes plus simples. En résolvant chaque sous-problème une seule fois et en stockant les résultats, cela évite les calculs redondants, conduisant à des solutions plus efficaces pour un large éventail de problèmes.

Concepts clés:

• Sous-structure optimale : La solution optimale à un problème peut être construite à partir des solutions optimales à ses sous-problèmes.
• Sous-problèmes qui se chevauchent : Les sous-problèmes sont souvent répétés dans le problème plus vaste, conduisant à des calculs redondants.
• Mémorisation / Tabulation : Stockage des solutions aux sous-problèmes pour éviter le recalcul.

Certains problèmes importants et les plus courants des algorithmes de programmation dynamique, que vous devez résoudre avant de continuer, sont :

Articles Liés:

• Tabulation vs mémorisation
• Comment résoudre un problème de programmation dynamique ?
• Tutoriel de programmation dynamique
• Top 50 des problèmes de codage de programmation dynamique pour les entretiens
• Problèmes pratiques sur l'algorithme de programmation dynamique

8. Algorithmes graphiques :

Algorithmes graphiques Les structures de données et les algorithmes (DSA) sont un ensemble de techniques et de méthodes utilisées pour résoudre des problèmes liés aux graphiques, qui sont un ensemble de nœuds et d'arêtes. Ces algorithmes sont conçus pour effectuer diverses opérations sur des graphiques, telles que chercher, parcourir, trouver le chemin le plus court , et déterminer connectivité . Ils sont essentiels pour résoudre un large éventail de problèmes du monde réel, notamment le routage du réseau, l’analyse des réseaux sociaux et l’allocation des ressources.

Rubriques connexes:

• Tutoriel graphique
• Top 50 des problèmes de codage graphique pour les entretiens
• Problème pratique sur les algorithmes graphiques

9 . Recherche de modèles

Recherche de modèles est une technique fondamentale du DSA utilisée pour rechercher les occurrences d'un modèle spécifique dans un texte donné.

Vous trouverez ci-dessous quelques algorithmes de recherche de modèles standard :

Rubriques connexes:

• Tutoriel de recherche de modèles
• Problème de pratique sur Recherche de modèles

dix . Algorithmes mathématiques

Algorithmes mathématiques sont une classe d'algorithmes qui résolvent des problèmes liés aux concepts mathématiques. Ils sont largement utilisés dans divers domaines, notamment l’infographie, l’analyse numérique, l’optimisation et la cryptographie.

Rubriques connexes:

• Problème pratique sur l'algorithme mathématique

11. Algorithmes géométriques

Algorithmes géométriques sont une classe d'algorithmes qui résolvent des problèmes liés à la géométrie. Les algorithmes géométriques sont essentiels pour résoudre un large éventail de problèmes en informatique, tels que :

Rubriques connexes:

• Problème pratique sur les algorithmes géométriques

12. Algorithmes au niveau du bit

Algorithmes au niveau du bit sont des algorithmes qui opèrent sur des bits individuels de nombres. Ces algorithmes manipulent la représentation binaire des nombres pour effectuer des tâches telles que la manipulation de bits, les opérations logiques au niveau du bit (AND, OR, XOR), décalage de bits , et paramètre ou effacer des bits spécifiques à l'intérieur d'un nombre. Les algorithmes bit à bit sont couramment utilisés dans tâches de programmation, de cryptographie et d'optimisation de bas niveau où une manipulation efficace de bits individuels est requise.

Rubriques connexes:

• Tutoriel sur les algorithmes bit à bit
• Problème pratique sur les algorithmes au niveau du bit

13. Algorithmes randomisés

Les algorithmes randomisés sont des algorithmes qui utilisent le hasard pour résoudre des problèmes. Ils utilisent des entrées aléatoires pour atteindre leurs objectifs, conduisant souvent à des solutions plus simples ou plus efficaces.

Types d'algorithmes randomisés :

tutoriel javafx

• Las Vegas : Produit toujours un résultat correct, mais le temps d'exécution est aléatoire.
• monte Carlo : Peut produire un résultat incorrect avec une faible probabilité, mais le temps d'exécution est généralement plus rapide.

Algorithmes importants qui utilisent des algorithmes de randomisation :

14. Algorithme de branchement et de liaison

Le Algorithme de branchement et de liaison est une méthode utilisée dans les problèmes d'optimisation combinatoire pour rechercher systématiquement la meilleure solution. Cela fonctionne en divisant le problème en sous-problèmes plus petits, ou branches, puis en éliminant certaines branches en fonction des limites de la solution optimale. Ce processus se poursuit jusqu'à ce que la meilleure solution soit trouvée ou que toutes les branches aient été explorées.

Problèmes standard sur l'algorithme de branchement et de liaison :

Rubriques connexes:

• Tutoriel sur l'algorithme de branchement et de liaison

En savoir plus sur les complexités

Dans les structures de données et les algorithmes (DSA), l'objectif principal est de résoudre les problèmes de manière efficace et efficiente. Pour déterminer l’efficacité d’un programme, nous examinons deux types de complexités :

1. Complexité temporelle : Cela nous indique combien de temps notre code met à s'exécuter.
2. Complexité spatiale : Cela nous indique la quantité de mémoire utilisée par notre code.

Notation asymptotique :

Pour comparer l'efficacité des algorithmes, nous utilisons la notation asymptotique, un outil mathématique qui estime temps basé sur taille d'entrée sans exécuter le code. Il se concentre sur le nombre d'opérations de base du programme.

La notation la plus couramment utilisée pour l'analyse de code est Notation grand O , fournissant une limite supérieure sur le temps d'exécution ou l'utilisation de la mémoire concernant la taille d'entrée.

Rubriques connexes:

• Comprendre la complexité temporelle avec des exemples simples
• Complexités temporelles des différentes structures de données
• Comment analyser les boucles pour l'analyse de la complexité des algorithmes
• Questions pratiques sur l'analyse de la complexité temporelle

Aide-mémoire pour les problèmes pratiques :

Listes organisées de problèmes à partir des articles ci-dessous :

• Feuille de route DSA par Sandeep Jain
• FEUILLE SDE – Un guide complet pour la préparation du SDE
• techcodeview.com Master Sheet - Liste de toutes les aide-mémoire