Aller au contenu

1NSI : Cours Complexité d'un Algorithme⚓︎

Introduction (\(\approx 28min\))⚓︎

Notion de Complexité⚓︎

La complexité d'un algorithme répond à la question suivante: Cet algorithme répond-il au problème posée en un temps raisonnable?

En effet, disposer d'un algorithme qui répond au problème posé mais dans un délai de plusieurs milliers/millions d'années n'est d'une utilité que très modeste.

Définition⚓︎

Complexité

La complexité d'un algorithme mesure le nombre de ressources nécessaires à l'exécution d'un algorithme. On distingue usuellement deux types de ressources:

  • Les ressources temporelles : le nombre d'instructions à exécuter. On parle dans ce cas de complexité en temps (ou temporelle)
  • Les ressources spatiales : la mémoire à utiliser. On parle dans ce cas de complexité en espace (ou spatiale)

Dépendance d'un paramètre \(n\)⚓︎

La complexité d'un algorithme dépend toujours d'un (ou de plusieurs) paramètre.s donné.s en entrée, qui sont un/des nombres entiers, souvent notés \(n\) (ou etc...) : L'entier \(n\) mesure la taille des données en entrée. On note \(C(n)\) la complexité de l'algorithme avec un paramètre \(n\) en entrée.

Exemples de paramètre \(n\) :

  • Entrées données sous forme de liste: Lorsque les entrées sont une liste de valeurs, alors la taille \(n\) des entrées mesure la taille de la liste, donc le nombre de valeurs de la liste
    • Exemple: Algorithme de tri: \(n\) est le nombre de valeurs à trier
  • Entrées sous forme d'un entier \(n\): Lorsque l'entrée est un nombre entier \(n\), alors la taille des entrées est le nombre de bits requis pour stocker cet entier \(n\) en mémoire. Nous verrons plus tard que, dans ce cas, la taille des entrées vaut \(\lceil log_2(n) \rceil\)
    • Exemple: Algorithme de factorisation d'un entier: \(n\) est le nombre de chiffres du nombre à factoriser

Complexité Asymptotique. Notation \(O()\)⚓︎

La complexité asymptotique d'un algorithme s'intéresse à la complexité de l'algorithme :

  • pour de grandes valeurs de \(n\) (on dit que \(n\) tend vers \(+\infty\), ou que \(n\) est proche de \(+\infty\)),
  • et à une (bonne) valeur approximative mais néanmoins représentative de la complexité de l'algorithme.

Exemples:

  • Si \(C(n)=2n+3\), Alors une valeur approximative mais néanmoins représentative de \(C(n)\) est \(2n\), ce qui revient à négliger le \(+3\). On dit que la complexité (asymptotique) est en \(O(n)\), lire " en grand \(O\) de \(n\) " . On note \(C(n) = O(n)\). On dit dans ce cas particulier que la complexité est linéaire (en \(an+b\)\(a\) et \(b\) sont des réels)
  • Si \(C(n)=n^2+bn+c\), Alors une valeur approximative mais néanmoins représentative de \(C(n)\) est \(n^2\), donc la complexité (asymptotique) est en \(O(n^2)\). On note \(C(n) = O(n^2)\). On dit dans ce cas particulier que la complexité est quadratique (en \(an^2\)\(a\) est un réel). Ce qui est un cas particulier de complexité polynômiale (en \(O(n^2)\), ou en \(O(n^3)\), ou en \(O(n^4)\), etc..).
  • Si \(C(n)=2^n+bn^2+bn+c\), Alors une valeur approximative mais néanmoins représentative de \(C(n)\) est \(2^n\), donc la complexité (asymptotique) est en \(O(2^n)\). On note \(C(n) = O(2^n)\). On dit dans ce cas particulier que la complexité est exponentielle (en \(2^n\), ou \(3^n\) etc..., plus généralement : en \(a\times b^n\)\(a\) est un réel et \(b\) un réel \(\gt0\))
  • ⚠ NOUVEAU ⚠ : Si \(C(n)=log_2(n)\), lire Logarithme (en base 2) de \(n\), Alors on dit que la complexité (asymptotique) est en \(O(log_2(n))\), ou que la complexité est logarithmique (de base 2).

    Fonction Logarithme de base 2

    • La fonction \(n \mapsto log_2(n)\), qui est en fait une restriction pour des valeurs entières \(n\), d'une fonction mathématique plus générale \(x \mapsto log_2(x)\) définie pour \(x\) réel \(\gt0\), est une nouvelle fonction, encore inconnue en 1ère. Voici quelques unes de ses propriétés:
    • Elle est connue pour croître très lentement vers \(+\infty\) lorsque \(n \rightarrow +\infty\) (encore plus lentement que la fonction \(n\mapsto\sqrt n\))

    Formulaire : fonction \(log_2\)

    • La fonction Logarithme en base 2 est la fonction réciproque de la fonction exponentielle de base 2, cela veut dire que: \(log_2(2^x) = x \,\,\,\,\,\) et \(\,\,\,\,\,2^{log_2(x)}=x\)
      En particulier : \(log_2(2)=1\,\,\,\,\,\) et \(\,\,\,\,\,log_2(1)=0\)
    • la fonction \(x \mapsto log_2(x)\) est une fonction strictement croissante sur l'intervalle \(]0;+\infty[\)
    • Le Logarithme en base 2 transforme un produit en somme \(log_2(xy) = log_2(x) + log_2(y)\)
    • En particulier, le Logarithme de base \(2\) transforme une multiplication par \(2\), en une addition de \(1\), cela veut dire que: \(log_2(2 \times x)=log_2(x)+1\)
    • le Logarithme en base 2 transforme une puissance en produit \(log_2(x^p) = p \times log_2(x)\)
  • ⚠ DISCLAIMER ⚠ ATTENTION, cette fonction Logarithme de base 2, notée \(\log_2(x)\), ou plus simplement, mais faussement, \(log(x)\) par les informaticiens (ce qui est une erreur de notation, donc faux!) n'est PAS (exactement) la même que la fonction dite LN, et notée \(ln(x)\), et appelée Logarithme népérien qui sera étudiée en mathématiques en Terminale. Elles sont en fait presque identiques (à un facteur multiplicatif près), mais PAS exactement les mêmes. Elles sont en fait reliées par la relation fondamentale suivante: Pour tout réel \(x\gt0, \,\,\,\,\,\, log_2(x)=\dfrac {ln(x)}{ln(2)}\)

Pire/Meilleur des cas. Cas moyen⚓︎

Noter également que l'on peut s'intéresser à plusieurs complexités distinctes qui ne sont pas obligatoirement égales entre elles (à priori), mais qui peuvent toutes être intéressantes, selon le ou les cas de figure qui nous intéresse(nt). On peut s'intéresser à la complexité:

  • au pire des cas
  • au meilleur des cas
  • au cas moyen

En général, on s'intéresse au pire des cas.

Méthodes de calcul de la complexité en temps⚓︎

On se donne un algorithme qui résoud un problème donné dont la taille des entrées est mesurée par un paramètre \(n\), donné en entrée. On cherche à connaître sa complexité en temps.

Algorithmes itératifs⚓︎

Dans certains cas particuliers simples (algorithmes itératifs), on peut tenter de compter manuellement le nombre d'instructions.

Exemples Classiques de Complexité⚓︎

Dans le cas général, il n'y a pas de méthode infaillible pour toutes les situations, mais une méthode pratique utile nommée master theorem permet de répondre dans certains cas usuels. Elle consiste à:

  • incrémenter (le paramètre \(n\))
  • et compter les (nouvelles) instructions
  • Comparer les deux complexités (avant et après l'incrémentation) (par exemple comparer \(C(n+1)\) avec \(C(n)\), ou bien \(C(2\times n)\) avec \(C(n)\))

Exemples à connaître en pratique, ou master theorem:

\(C(n+1)=C(n)\)⚓︎

Complexité Constante

Si \(C(n+1)=C(n)\), alors la complexité est constante : on dit/note aussi que la complexité est en \(O(1)\)

Remarquer que:

  • Si \(f(n)=C^{te}\), alors \(f(n+1)=C^{te}=f(n)\)
  • Autrement dit, l'équation fonctionnelle sur la complexité est cohérente avec la formule suivante des fonctions constantes:

\(C^{te} \, \text{pour } f(n+1)=C^{te} \, \text{pour } f(n)\)

\(C(n+1)=C(n)+a\)⚓︎

Complexité Linéaire

Si \(C(n+1)=C(n)+a\) pour \(a\) réel (constant), alors la complexité est linéaire (ATTENTION: mathématiquement, il faudrait dire affine) donc la complexité est en \(O(n)\)

Remarquer que:

  • Si \(f(n)=an +b\) est une fonction linéaire (il faudrait dire affine), alors \(f(n+1)=a(n+1)+b=an+a+b=(an+b)+a=f(n)+a\)
  • Autrement dit, l'équation fonctionnelle précédente sur la complexité \(C(n)\) est cohérente avec la formule suivante des fonctions linéaires (il faudrait dire affine):

\(a(n+1)+b=(an+b)+a\)

\(C(n+1)=C(n)+an\)⚓︎

Complexité Quadratique

Si \(C(n+1)=C(n)+an\), alors la complexité est quadratique donc la complexité est en \(O(n^2)\)

Remarquer que:

  • Si \(f(n)=an^2\) est une fonction quadratique (on pourrait considérer une fonction plus générale \(f(n)=an^2+bn+c\)), alors \(f(n+1)=a(n+1)^2=a(n^2+2n+1)=an^2+2an+a= f(n)+2an+a\approx f(n)+a'n\)
  • Autrement dit, l'équation fonctionnelle précédente sur la complexité \(C(n)\) est cohérente avec la formule approchée suivante des fonctions quadratiques:

\(a(n+1)^2\approx an^2+a'n\)

\(C(n+1)=C(n) + \varepsilon\)⚓︎

Complexité un peu plus subtile : à Préciser

Si \(C(n+1)=C(n) + \varepsilon \)\(\varepsilon\) est un réel \(\gt0\) mais petit (c'est-à-dire proche de zéro) et pouvant de plus être variable (dépendant de \(n\)), alors ceci est un cas un peu plus subtil et cela dépend des situations...

Complexité Logarithmique. un Cas Particulier très important

Si \(C(2\times n)=C(n)+1\), Alors on dit dans ce cas que la complexité est Logarithmique (de base 2), et (notation) que la complexité est en \(O(log_2(n))\)

Remarquer que :

  • Si \(f(n)=log_2(n)\) est la fonction logarithme de base \(2\), alors \(f(2\times n)=log_2(2\times n)=log_2(n)+1=f(n)+1\)
  • Autrement dit, l'équation fonctionnelle précédente sur la complexité \(C(n)\) est cohérente avec la formule suivante des fonctions logarithmes de base \(2\):

\(log_2(2\times n)=log_2(n)+1\)

⚠ Intuitivement ⚠

La complexité logarithmique (de base 2) correspond à une situation où la multiplication par \(2\) de la taille \(n\) des données en entrée, équivaut à l'addition de \(1\) unité supplémentaire de complexité (classiquement, \(1\) itération de boucle supplémentaire)

\(C(n+1)=2\times C(n)\)⚓︎

Complexité Exponentielle

Si \(C(n+1)=2\times C(n)\), alors la complexité est exponentielle plus précisément la complexité est en \(O(2^n)\).

Remarquer que :

  • Si \(f(n)=2^n\) est la fonction exponentielle de base \(2\), alors \(f(n+1)=2^{n+1}=2\times2^n=2\times f(n)\)
  • Autrement dit, l'équation fonctionnelle précédente sur la complexité \(C(n)\) est cohérente avec la formule suivante des fonctions exponentielles de base \(2\):

\(2^{n+1}=2\times2^n\)

⚠ Intuitivement ⚠

La complexité exponentielle (de base 2) correspond à une situation où l'augmentation/addition de \(1\) pour la taille des données en entrée, équivaut à multiplier par \(2\) la complexité.

Remarque: Ces résultats se généralisent parfaitement, en adaptant les passages correspondant, à :

  • des exponentielles de base \(3\): Si \(C(n+1)=3\times C(n)\) Alos \(C(n)=O(3^n)\)
  • des exponentielles de base \(4\): Si \(C(n+1)=4\times C(n)\) Alos \(C(n)=O(4^n)\), etc...

Master Theorem⚓︎

Résumé : Master Theorem

Le tableau suivant résume les complexités des fonctions récursives:

> Relation de Récurrence Complexité
> \(C(n+1)=C(n)\) \(O(1)\)
> \(C(n+1)=C(n)+O(1)\) \(O(n)\)
> \(C(n+1)=C(n)+O(n)\) \(O(n^2)\)
> \(C(n+1)=C(n)+ \varepsilon\)
pour \(\varepsilon>0\) et variable (avec \(n\))
cas plus subtil:
ça dépend (de \(\varepsilon\))
Exemple 1 \(C(2\times n)=C(n)+ O(1)\) \(O(log_2(n))\)
Exemple 2 \(C(a\times n)=C(n)+ O(1)\) \(O(log_a(n))\)
> \(C(n+1)=2\times C(n)+ O(1)\) \(O(2^n)\)
> \(C(n+1)=a\times C(n)+ O(1)\) \(O(a^n)\)

Exemples Pratiques de Complexités en temps⚓︎

Soit un algorithme qui demande en entrée le nombre \(n\) de jours restant avant le bac, et qui prépare un élève au bac.

Complexité Constante⚓︎

Considérons l'algorithme en pseudo-code suivant:

Saisir n
faire 100 exercices

L'algorithme consiste à préparer 100 exos pour être prêt pour le bac. Ainsi le nombre d'exercices à faire est indépendant de \(n\), donc \(C(n+1)=C(n)\), donc la complexité en temps est constante: en \(O(1)\)

Complexité linéaire⚓︎

Supposons qu'il reste au moins 2 jours avant le bac. Considérons maintenant l'algorithme suivant:

Saisir n
m prend la valeur n
Tant que m1:
  faire 1 exercice
  m prend la valeur m-1

Cet algorithme modélise un élève qui va faire un exercice par jour, tous les jours, jusqu'au jour du bac.

Ainsi \(C(n+1) = C(n)+1\), donc la complexité en temps est linéaire: en \(O(n)\)

Complexité Logarithmique⚓︎

Considérons maintenant l'algorithme:

Saisir n
m prend la valeur n
Tant que m1:
  faire 1 exercice
  m prend la valeur m/2        #partie entière supérieure de m/2

Un élève fait \(1\) exercice, puis il divise le nombre de jours restants par \(2\) et il l'arrondit à sa partie entière supérieure, puis il recommence.

Ainsi \(C(2\times n)=C(n)+1\), donc la complexité en temps est logarithmique: en \(O(log_2(n))\)

Complexité Quadratique⚓︎

Supposons qu'il reste au moins 2 jours avant le bac.

Considérons l'algorithme suivant

Saisir n
m prend la valeur n
Tant que m1:
  faire n exercices
  m prend la valeur m-1

Cet algorithme modélise un élève qui va faire \(n\) exercices par jour, tous les jours, jusqu'au jour du bac.

Ainsi \(C(n+1) = C(n)+n\), donc la complexité en temps est quadratique, en \(O(n^2)\).

Remarque intuitive:
Tout se passe comme si il y avait deux boucles imbriquées:

  • \(1\) boucle de \(1\) à \(n\) pour le nombre \(m\) de jours restants
  • \(1\) boucle de \(1\) à \(n\) pour le nombre d'exercices à faire

et l'on remarque que \(n\times n=n^2\) Si de plus, pour chaque exercice réalisé, l'élève refait \(n\) variantes de l'exercice, alors on aurait \(3\) boucles imbriquées (de \(1\) à \(n\)) et on aurait une complexité en temps cubique: en \(O(n^3)\) donc en temps polynômial.

Complexité Exponentielle⚓︎

Supposons qu'il reste au moins 2 jours avant le bac.

Considérons l'algorithme suivant

Saisir n
m prend la valeur n
m' prend la valeur 1
Tant que m>=1:
  faire m' exercices
  m' prend la valeur m'*2
  m prend la valeur m-1

Cet algorithme utilise une variable supplémentaire \(m'\) contenant le nombre d'exercices à faire par jour. Chaque jour, un élève va faire le double d'exercices que le jour précédent, jusqu'au jour du bac.

Ainsi \(C(n+1) = 2\times C(n)\), donc la complexité en temps est exponentielle, plus précisément en \(O(2^n)\).