Introduction

Pour construire ce cours, je me suis appuyé sur celui ci : http://www.monlyceenumerique.fr/nsi_premiere/algo_a/a2_complexite.php.

La notion de complexité est fondamentale en informatique. Un des plus grands problèmes d'informatique théorique (pas encore résolu, alors n'hésitez pas à tenter votre chance) est en rapport avec la complexité : https://fr.wikipedia.org/wiki/Probl%C3%A8me_P_%E2%89%9F_NP.

A notre niveau nous ferons une utilisation plus pratique et donc moins théorique de la complexité. Elle nous permettra d'analyser nos algorithmes et de déterminer en général le temps d'exécution sans que ce temps soit lié à une machine particulière. Si mon algorithme tourne sur une Apple watch ou sur un ordinateur ultra puissant, je souhaite quand même que la complexité soit la même dans les deux cas.

Pour cela nous allons nous appuyer sur les mathématiques (comme d'habitude j'ai envie de dire).

Notion de fonction en mathématiques

Pour comprendre la notion de complexité, il faut comprendre la notion de fonction (à variable réelle) en mathématiques que vous avez vu en seconde.

Une fonction associe à chaque élément de son ensemble de définition au plus une valeur dans un ensemble d'arrivée. Par exemple pour la fonction inverse :

\(\mathbb R^{*} \to\mathbb R\)
\(x \to \frac{1}{x}\)

Nous allons associer à la taille des données en entrée \(n\) des unités de temps.

\(n \to T(n)\)

Coût en temps

Le pire des cas

Nous nous intéresseront avant tout à la complexité en temps dans "le pire des cas", et non en espace (mémoire).

Le pire des cas signifie que nous étudierons le cas le moins favorable à notre algorithme.

Supposons que je souhaite chercher l'as de pique dans un tas de 52 cartes qui sont toutes retournées et non triées. Chaque comparaison entre la carte que j'ai retournée et l'as de pique comptera pour une opération.

Question

• Dans le pire des cas, combien de cartes devrais-je retourner avant de trouver la carte que je cherche ?
• Plus généralement dans le cas où j'ai n cartes, combien de cartes devrais-je retourner avant de trouver la carte que je cherche ?

Calculer la complexité d'un algorithme

Une opération correspond à une unité de temps. Attention, ici le temps n'a pas de mesure : le temps n'est pas en seconde par exemple, c'est un temps théorique, abstrait.

Les opérations qui vont devoir être comptabilisées auront les coûts suivant :

Les affectations comptent pour 1 unité de temps :

a ← 2

Les comparaisons (comme les tests) comptent pour 1 unité de temps :

2 < 3

L'accès aux mémoires comptent pour une 1 unité de temps :

Lire a

Chaque opération élémentaire comptent pour une 1 unité de temps :

3 + 2
12 * 35

A noter

On ne prendra pas en compte les appels à la fonction print et on considérera que l'appel au range dans une boucle est exécuté une seule fois. Par exemple range(a + 1) aura un coût de 2 car on a une addition et une lecture de la variable a en mémoire.

Complexité constante

Un premier exercice

1 def conversion(n : float) -> tuple:
2   h = n // 3600
3   m = (n - 3600 * h) // 60
4   s = n % 60
5   return h, m, s

Dans les cas ci-dessus la complexité ne dépend pas de la taille de \(n\) (en fait c'est un peu plus compliqué que cela). On dira que la complexité est constante.

Cas des structures conditionnelles :

def puissanceMoinsUn(n:int)->int:
    if n%2==0:
        res = 1
    else:
        res = -1
    return res

Question

D'après vous quel est la complexité de cet algorithme ?

Complexité linéaire

Nous allons étudier la complexité de cet algorithme :

def sommeEntiers1(n:int)->int:
    somme = 0
    for i in range(n+1):
        somme += i
    return somme

Exercice

Déterminer la complexité dans le pire des cas de cet algorithme :

entier RechercheSéquentielle(tableau T, entier x) :
    Pour i variant de 0 à n-1
    Faire
        Si x==T[i]
            Alors Retourner i
        FinSi
    FinPour
    Retourner -1

Boucles imbriquées

Une boucle imbriquée consiste à exécuter une boucle dans une autre boucle :

chaine = ''
for lettre in 'ABCDEF': # Boucle extérieure
    ligne = lettre
    for nombre in range(1, 6):  # Boucle intérieure
        ligne = ligne + str(nombre)

    chaine = chaine + ligne + '\n'
print(chaine)

Question

Que va afficher le code ci-dessus ?

Dans le cas de boucles imbriquées, il peut être plus difficile de déterminer la complexité.

On calculera dans un premier temps la complexité de la boucle interne car on en a besoin pour connaître le coût d’une itération de la boucle externe.

De fait, souvent on va multiplier entre elles le nombre d’itérations de chacune des boucles.

Exercice

Déterminer la complexité de cet algorithme :

def Somme_messages(Tab1):
    somme = 0
    for i in range(n):
        for j in range(n):
            somme = somme + Tab1[i][j]
    return somme

Voici un exemple plus complexe où l'indice j dépend de l'indice i :

Les différentes classes de complexité

Le coût (en temps) d'un algorithme est l'ordre de grandeur du nombre d'opérations arithmétiques ou logiques que doit effectuer un algorithme pour résoudre le problème auquel il est destiné.

Cet ordre de grandeur dépend évidemment de la taille \(n\) des données en entrée.

On parlera de :

• Coût constant s'il ne dépend pas de la taille de \(n\) coût linéaire s'il est "d'ordre" \(n\)
• Coût quadratique s'il est "d'ordre" \(n^2\)
• Coût exponentielle si "l'ordre" est de la forme d'une puissance où \(n\) apparaît en exposant

O	Type de complexité
O(1)	constante
O(log(n))	logarithmique
O(n)	linéaire
O(n×log(n))	quasi-linéaire
O(n2)	quadratique
O(n3)	cubique
O(2n)	exponentielle
O(n!)	factorielle

Les différentes courbes représentatives :

Question

Dans notre cas on s'intéresse en particulier aux puissances de deux, pourquoi à votre avis ?

Concrètement si on exécute un algorithme avec une certaine complexité théorique, voici les résultats qu'on pourrait obtenir:

Tout ceci montre également l'importance pratique de ces considérations théoriques.

Les fonctions logarithme et exponentielle.

Ces deux fonctions sont fondamentales car elles permettent de modéliser un bon nombre de phénomènes en sciences naturelles ou physiques notamment.

D'un point de vu non rigoureux et naif on voit que la fonction exponentielle "croît rapidement" alors que la fonction logarithme népérien (\(ln\)) semble être "la même" fonction mais qui "croît lentement".

Dans notre cas elles nous permettront de modéliser des complexités en temps.

Récriproque

Comme le montre ce graphique ces deux fonctions sont liées :

En effet la courbe représentative de la fonction exponentielle est symétrique à celle de la fonction logarithme népérien par rapport à la droite d'équation \(y = x\).

Cela signifie d'un point de vue algébrique que la fonction logarithme népérien est la réciproque de la fonction exponentielle.

Ensemble de définitions

La fonction exponentielle est définie sur \(\mathbb{R}\) et est strictement positive.

Question

Sachant que la fonction logarithme est symétrique à la fonction exponentielle, et en étudiant les courbes représentants ces deux fonctions, quel devraît être l'ensemble de définition de la fonction logarithme ?

Base

Nous avons dit que la fonction \(2^n\) était exponentielle, c'est bien le cas mais sa fonction réciproque n'est pas le logarithme népérien mais le logarithme base 2.

En effet, à chaque fonction exponentielle on peut associer une base \(a\) telle que :

\(exp_{a}(x) = a^x = e^{x ln(a)}\)

Dans le cas où \(a = e\) où \(e\) représente la constante \(e\). Pour le logarithme on parle de logarithme népérien et nous avons : \(ln_{e} = 1\) d'où \(exp_{e}(x) = e^x = e^{x ln(e)}\)

Dans le cas où \(a = 2\), nous avons : \(log_{2}(2) = 1\)

Exercice

Complétez : dans le cas où \(a = 10\), nous avons \(log_{...}(...) = 1\).

On définit le logarithme base \(a\) de cette manière :

\(log_{a}(x) = \frac{ln x}{ln a}\)

Exercice

Montrer qu'on retrouve bien \(log_{a}(a) = 1\)

Définitions plus rigoureuses de la complexité

Même si les définitions rigoureuses de la complexité son hors programme, j'ai souhaité vous fournir quelques indications à ce sujet au cas où vous souhaiteriez approfondir ce sujet.

Nous avons parlé de \(O(n)\) mais sans définir précisément cette notation.

Cette notation est dite notation de Landau, du nom du mathématicien Edmund Landau.

La définition rigoureuse est celle ci :

Soit f, g deux fonctions. Alors dire que \(f(n) = O(g(n))\) qui se lit "f est un grand O de g", signifie :

  

Dans notre cas on peut ignorer les valeurs absolues car on ne considère que des valeurs positives.

De manière informelle cela revient à dire que la fonction |f| est majorée par la fonction |g| asymptotiquement, à un facteur près.

De manière similaire on peut définir le fait que |f| est minorée par |g| (à un facteur près). Ce que l'on note \(f(n) = \Omega(g(n))\).

Il existe d'autres notations, comme f(n) = Θ(g(n)). Je vous laisserai revenir vers moi à ce sujet si vous avez des questions.

Vous trouvez plus d'informations sur cet excellent site : https://zanotti.univ-tln.fr/ALGO/I31/Asymptotiques.html