Bases des algorithmes et méthodes d'analyse

Dans le monde de l'informatique,Les algorithmessont comme une recette pour un ordinateur. Il s'agit d'une séquence d'instructions claire, finie et exécutable, utilisée pour résoudre un problème spécifique ou accomplir une tâche computationnelle particulière. Que ce soit le logiciel de navigation sur votre téléphone qui planifie l'itinéraire le plus court pour vous, ou un moteur de recherche qui trouve les pages web les plus pertinentes parmi des masses de données en quelques millisecondes, tous deux reposent sur des algorithmes soigneusement conçus en arrière-plan.

Comprendre les fondamentaux des algorithmes et les méthodes d'analyse est une étape clé pour chaque programmeur afin de passer d'un implémenteur de code à un résolveur de problèmes.

Cet article vous présentera systématiquement les concepts clés des algorithmes et vous apprendra à évaluer scientifiquement les avantages et les inconvénients d'un algorithme.

Les caractéristiques essentielles des algorithmes

Un algorithme qualifié doit posséder les cinq caractéristiques de base suivantes. Nous pouvons les comprendre à l'aide d'une analogie culinaire :

  1. Finitude: L'algorithme doit se terminer après un nombre fini d'étapes. Tout comme une recette ne peut pas exiger que vous remuiez indéfiniment jusqu'à la fin de l'univers, elle doit donner une condition d'arrêt claire.
  2. Déterminisme: Chaque étape de l'algorithme doit avoir une définition exacte, sans ambiguïté. Par exemple, « ajouter une pincée de sel » est incertain, tandis que « ajouter 5 grammes de sel » est défini.
  3. Faisabilité: Chaque opération de l'algorithme doit être élémentaire et exécutable. Vous ne pouvez pas écrire dans une recette « utilisez votre esprit pour fouetter les œufs ».
  4. Entrée: Un algorithme a zéro ou plusieurs entrées. Ces entrées sont les objets traités par l'algorithme, tout comme les ingrédients nécessaires dans une recette.
  5. Sortie: Un algorithme a une ou plusieurs sorties. La sortie est une quantité qui a une relation spécifique avec l'entrée et qui est le résultat de l'exécution de l'algorithme, tout comme le plat final préparé.

Comment décrire un algorithme ?

Nous pouvons décrire un algorithme de nombreuses façons ; les trois plus courantes sont :

1. Description en langage naturel

Décrire les étapes de l'algorithme en langage humain (par exemple, chinois, anglais). L'avantage est qu'il est facile à comprendre, mais l'inconvénient est qu'il n'est pas assez précis et peut facilement prêter à ambiguïté.

Exemple: Trouver la valeur maximale parmi trois nombres.

  1. Comparez le premier nombre et le deuxième nombre, et mémorisez le plus grand.
  2. Comparez le nombre mémorisé à l'étape précédente avec le troisième nombre.
  3. Affichez le plus grand nombre comme valeur maximale.

2. Organigramme

Utilisez des symboles graphiques pour représenter le flux de contrôle de l'algorithme. Il montre intuitivement les relations logiques entre les étapes.

Description de l'organigramme : Ce diagramme montre clairement le processus de décision de l'algorithme pour trouver le maximum de trois nombres. Les losanges représentent des jugements conditionnels, les rectangles représentent des étapes de traitement, et les flèches indiquent le sens d'exécution du programme.

3. Pseudo-code

Une méthode de description entre le langage naturel et le langage de programmation. Elle utilise des structures semblables à celles d'un langage de programmation (par exemple,if, for, while), mais ignore les détails syntaxiques spécifiques et se concentre sur l'expression logique.

算法：FindMax
输入：三个数字 a, b, c
输出：最大值 max

1.  if a > b then
2.      max = a
3.  else
4.      max = b
5.  end if
6.  if c > max then
7.      max = c
8.  end if
9.  输出 max

4. Implémentation dans un langage de programmation

En fin de compte, l'algorithme doit être traduit en code dans un langage de programmation (comme Python, Java, C++) afin de s'exécuter sur un ordinateur.

Exemple

# Implémentation en Python : trouver le maximum de trois nombres
def find_max(a, b, c):
    # Comparer d'abord a et b, affecter la plus grande valeur à max_value
    if a > b:
        max_value = a
    else:
        max_value = b
    # Comparer ensuite max_value avec c
    if c > max_value:
        max_value = c
    return max_value

# Code de test
print(find_max(5, 9, 3))  # Sortie : 9
print(find_max(-1, 0, 1)) # Sortie : 1

Résultat de sortie :

9
1

Analyse d'algorithmes : comment évaluer la qualité d'un algorithme ?

Concevoir un algorithme capable de résoudre un problème n'est que la première étape ; nous devons aussi déterminer quel algorithme est meilleur. Habituellement, nous évaluons selon deux dimensions :

1. Complexité temporelle

Il mesureLe temps nécessaire à l'exécution d'un algorithmecomment, à mesure quela taille des données d'entrée (n)augmente avec la croissance de ... Ce sur quoi nous nous concentrons n'est pas le nombre précis de secondes, mais la tendance de croissance (appeléecomplexité temporelle asymptotique）。

Comparaison des complexités temporelles courantes :

Complexité Name Exemple (n = taille des données) Métaphore imagée
O(1) Ordre constant Accès aux éléments d'un tableau par index « Allumer la lumière ». Peu importe la taille de la pièce, le temps pour actionner l'interrupteur est le même.
O(log n) Ordre logarithmique Recherche binaire "Feuilleter le dictionnaire". À chaque fois, la moitié est éliminée, donc la vitesse de recherche est extrêmement rapide.
O(n) Ordre linéaire Parcourir le tableau Compter les personnes. Compter personne par personne ; le temps est proportionnel au nombre total de personnes.
O(n log n) Ordre linéarithmique Tri rapide, tri fusion "Tri par diviser pour régner". Bien plus rapide que O(n²).
O(n²) Ordre quadratique Tri par sélection simple, tri à bulles "Poignées de main deux à deux". Chaque personne doit serrer la main de chaque autre personne une fois.
O(2ⁿ) Ordre exponentiel Résolution des Tours de Hanoï, énumération par force brute "Division cellulaire". La croissance est extrêmement terrifiante ; un n légèrement plus grand devient insupportable.

Comment analyser ?Concentrez-vous sur les boucles et la récursivité.

  • Boucle simple : généralement O(n).
  • Boucles imbriquées : généralement O(n²) (si les deux niveaux sont liés à n).
  • Stratégie de recherche binaire : généralement O(log n).

2. Complexité spatiale

Il mesureL'espace mémoire nécessaire à l'exécution d'un algorithmecomment, au fur et à mesure quela taille des données d'entrée (n)augmente avec la croissance de ... En plus de stocker les données d'entrée elles-mêmes, il est également nécessaire de prendre en compte les tableaux supplémentaires, variables, etc. alloués pendant l'exécution de l'algorithme.

Analyse de l'exemple :

Exemple

# Exemple 1 : complexité spatiale O(1)
def find_max_in_list(lst):
    max_val = lst[0]          # Utilise uniquement un nombre constant de variables supplémentaires.
    for num in lst:
        if num > max_val:
            max_val = num
    return max_val

# Exemple 2 : complexité spatiale O(n)
def copy_and_double_list(lst):
    new_list = []             # Allocation d'une nouvelle liste de même longueur que la liste d'entrée.
    for num in lst:
        new_list.append(num * 2)
    return new_list

Exercice pratique : analyse et application du point de vue des algorithmes de tri

Prenons l'exemple classique dutri à bulles, en appliquant de manière exhaustive les connaissances ci-dessus.

Idée de l'algorithme

Parcourir de façon répétée la liste à trier, en comparant deux éléments adjacents à la fois, et les échanger s'ils sont dans le mauvais ordre.

Le parcours de la liste est répété jusqu'à ce qu'il n'y ait plus d'éléments à échanger, ce qui signifie que la liste a été triée. Les éléments plus petits remonteront progressivement vers le haut de la séquence comme des bulles.

Implémentation Python et analyse ligne par ligne

Exemple

def bubble_sort(arr):
    """
Algorithme de tri à bulles
Paramètre arr : la liste à trier
Valeur de retour : la liste triée (modifiée sur place, également renvoyée directement)
    """
    n = len(arr)
    # Boucle externe : contrôle combien de tours de « bullage » sont nécessaires au total.
    for i in range(n - 1):
        # On suppose que ce tour est déjà trié, ce qui sert à l'optimisation.
        swapped = False
        # Boucle interne : effectue une passe de bullage, faisant descendre le plus grand élément à la fin.
        # Après chaque tour, les i+1 derniers éléments sont déjà triés, donc l'intervalle est n-1-i.
        for j in range(0, n - 1 - i):
            # Si l'élément précédent est plus grand que celui qui le suit, on échange.
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # La syntaxe d'échange élégante de Python.
                swapped = True  # Un échange a eu lieu.
        # Si aucun échange ne se produit pendant ce tour, la liste est entièrement triée, donc nous pouvons sortir plus tôt.
        if not swapped:
            break
    return arr

# Données de test et vérification.
test_data = [64, 34, 25, 12, 22, 11, 90]
print("Avant le tri :", test_data)
sorted_data = bubble_sort(test_data.copy()) # Utiliser copy pour éviter de modifier la liste d'origine.
print("Après le tri :", sorted_data)

# Vérifier si le résultat est correct.
print("Le tri est-il correct ?", sorted_data == sorted(test_data.copy())) # Devrait être cohérent avec le résultat du tri intégré de Python.

Résultat de sortie :

排序前: [64, 34, 25, 12, 22, 11, 90]
排序后: [11, 12, 22, 25, 34, 64, 90]
排序是否正确? True

Analyse de l'algorithme

  • Complexité temporelle：
    • Pire cas et cas moyen O(n²): Lorsque la liste est complètement inversée, il est nécessaire d'effectuer(n-1) + (n-2) + ... + 1 = n(n-1)/2comparaisons et échanges.
    • Meilleur cas O(n): Lorsque la liste est déjà triée, en ajoutantswappedAvec l'optimisation du drapeau, un seul parcours suffit pour détecter l'absence d'échanges et terminer prématurément.
  • Complexité spatiale O(1): L'algorithme n'utilise quei, j, swappedet d'autres variables temporaires en quantité fixe, estun algorithme de tri en place.

Exercices pratiques

  • Simulation manuelle: Utilisez du papier et un crayon pour dérouler l'algorithme, pour la liste[5, 3, 8, 1]Effectuez le tri, et écrivez l'état de la liste après chaque passe de bullage.
  • Expérience sur la complexité: Modifiez les données de test, et testez avec des listes déjà triées (par exemple,[1,2,3,4,5]) et une liste complètement inversée (telle que[5,4,3,2,1]) pour observer le nombre de boucles (vous pouvez ajouter un compteur dans la boucle interne).
  • Essayez d'améliorer: Pouvez-vous penser à un algorithme de tri qui s'apparente dans l'idée au tri à bulles mais potentiellement plus efficace ? (Indice : chaque parcours ne fait pas seulement remonter une bulle maximale, mais fait aussi descendre une bulle minimale.)
autres extensions