Structures de Données - Complexité des Algorithmes

Study Notes

Cours de Structures de Données en Cycle Ingénieur

Objectifs: Comprendre la notion de complexité pour étudier l'efficacité des programmes.
Séance 1: Analyse de la complexité des algorithmes.
Concepts fondamentaux:
- Complexité en temps: Évaluation du temps d'exécution d'un algorithme.
- Complexité en espace: Évaluation de l'espace mémoire occupé par l'exécution d'un algorithme.
- Exemple: Échange de deux valeurs entières. Méthodes 1 et 2 sont présentées, illustrant une méthode qui utilise une variable supplémentaire et une autre qui n'en utilise pas.
Préambule & Introduction:
- Ada Lovelace: Pionnière dans le domaine de la programmation informatique, avec des travaux sur la machine analytique de Charles Babbage.
- Objectifs des calculs de complexité: Prévoir les temps d'exécution et comparer différents algorithmes réalisant le même traitement.
Types de complexité:
- Complexité constante (O(1)): Le temps d'exécution reste constant quel que soit l'entrée.
- Complexité logarithmique (O(log n)): Le temps d'exécution croit logarithmiquement avec la taille de l'entrée.
- Complexité linéaire (O(n)): Le temps d'exécution croit linéairement avec la taille de l'entrée.
- Complexité quasi-linéaire (O(n log n)): Le temps d'exécution est un multiple de la complexité logarithmique de l'entrée.
- Complexité quadratique (O(n²)): Le temps d'exécution croit quadratique avec la taille de l'entrée.
- Complexité cubique (O(n³)): Le temps d'exécution croit au cube de la taille de l'entrée.
Paramètre de complexité : La grandeur utilisée pour quantifier les données d'entrée, comme la taille d'un tableau (n).

Notions de Big O

Paramètre de complexité: La taille de l'entrée (souvent notée n).
Types d’instructions: L'analyse de la complexité se concentre sur les opérations élémentaires (affectations, comparaisons, etc.)
Analyse du pire des cas (Big O): Détermine la borne supérieure du temps d'exécution d'un algorithme.
Expression asymptotique: Garder le terme de plus haut degré dans l'expression de complexité.
Complexité constante (O(1)): Temps d'exécution indépendant de la taille de l'entrée.
Complexité linéaire (O(n)): Temps d'exécution proportionnel à la taille de l'entrée.
Complexité quadratique (O(n²)): Temps proportionnel au carré de la taille de l'entrée.

Notion de Big Omega

Borne inférieure asymptotique: Définie une borne inférieure pour le temps d'exécution.

Notion de Big Theta

Borne supérieure et inférieure simultanées: Décrit les conditions où une fonction est à la fois inférieure et supérieure à une autre fonction.
Complexité équivalente: Les fonctions ayant la même complexité Θ sont considérées comme équivalentes.

Cas particulier : Complexité des fonctions de référence

Comparaison: Comparer des complexités en se référant aux fonctions de base en utilisant les notations « Big O, Big Omega, Big Theta »

Calcul de la complexité

Préambule: La complexité est le temps/espace nécessaire à l'exécution d'un algorithme.
Méthodes: Analyse d'opérations simples, analyse des boucles, etc.
Simplification: Ne pas se concentrer sur les constantes multiplicatives ou les constantes additives.
Exemple de calcul: Fournir des exemples de calcul de complexité pour illustrer comment calculer la complexité d'un algorithme.

Caractéristiques de la complexité Big O

Mesure du temps / espace: la complexité mesure le temps ou l’espace mémoire nécessaire pour un algorithme.
Ignorer les constantes: L'analyse se concentre sur les facteurs principaux qui évoluent avec la taille des données.
Représenter avec le Big O: Illustrer comment simplifier une expression mathématique en fonction du Big O, et supprimer des valeurs constantes ou additives.