Complexité d'un algorithme

Evaluer le temps et la mémoire nécessaire pour exécuter un algorithme.

Mesure du temps d'exécution (utilisation du module time)

from time import time
t1 = time()

t2 = time()
print(t2 - t1)

Exemple 1 : test de primalité

from time import time
def prem1(n):
    """retourne True si l'entier n est premier et False sinon"""
    if n <= 1:
        return False
    T=True
    i = 2
    while i < n:
        if n%i == 0:
            T = False
        i = i+1
    return T    

t1 = time()
print(prem1(1000003))
t2 = time()
print("temps de calcul = ", t2 - t1, "secondes")

t1 = time()
print(prem1(1000002))
t2 = time()
print("temps de calcul = ", t2 - t1, "secondes")

Complexité en $O(n)$

def prem2(n):
    """retourne True si l'entier n est premier et False sinon"""
    if n <= 1:
        return False
    i = 2
    while i < n:
        if n%i == 0:
            return False
        i = i+1
    return True    

t1 = time()
print(prem2(1000003))
t2 = time()
print("temps de calcul = ", t2 - t1, "secondes")

t1 = time()
print(prem2(1000002))
t2 = time()
print("temps de calcul = ", t2 - t1, "secondes")

Complexité en $O(n)$ dans le pire des cas et en $O(1)$ dans le meilleur des cas.

def prem3(n):
    """retourne True si l'entier n est premier et False sinon"""
    if n <= 1:
        return False
    i = 2
    while i**2 <= n:
        if n%i == 0:
            return False
        i = i+1
    return True  

t1 = time()
print(prem3(1000003))
t2 = time()
print("temps de calcul = ", t2 - t1, "secondes")

t1 = time()
print(prem3(1000002))
t2 = time()
print("temps de calcul = ", t2 - t1, "secondes")

Complexité en $O(\sqrt{n})$ dans le pire des cas et en $O(1)$ dans le meilleur des cas.

Vocabulaire

On note $T(n)$ le nombre d'opérations pour traiter le nombre $n$, un objet de longueur $n$ ...

• Complexité logarithmique : $T(n)=O(\ln(n))$
• Complexité linéaire : $T(n)=O(n)$
• Complexité polynomiale : $T(n)=O(n^k)$ (avec $k\geqslant2$)
• Complexité exponentielle : $T(n)=O(\lambda^n)$ (avec $\lambda>1$)
• Complexité dans le meilleur des cas
• Complexité dans le pire des cas

Exemple 2 : calcul de $a^n$

def puiss(a,n):
    """a est un réel et n un entier naturel non nul"""
    R=1
    for i in range(n):
        R=R*a
    return R

puiss(2,10)

Complexité en $O(n)$ : linéaire

def puiss(a,n):
    """a est un réel et n un entier naturel non nul"""
    R = 1
    while n > 0:
        if n%2 == 1:
            R = R*a
        a = a**2
        n = n//2
    return R

puiss(2,10)

Combien d'itérations de la boucle while ?

Complexité ?

Si $2^p\leqslant n_k<2^{p+1}$

alors $2^{p-1}\leqslant \dfrac{n_k}2<2^{p}$

et donc $2^{p-1}\leqslant n_{k+1} = \left\lfloor\dfrac{n_k}2\right\rfloor<2^{p}$

Si $2^p\leqslant n_k<2^{p+1}$, il y a $p+1$ itérations de la boucle while

Il y a donc $1+\left\lfloor\dfrac{\ln n}{\ln 2}\right\rfloor$ itérations de la boucle.

Complexité en $O(\ln(n))$ : complexité logarithmique

Version récursive

def puiss(a,n):
    if n == 0:
        return 1
    if n%2 == 1:
        return a*puiss(a**2,n//2)
    return puiss(a**2,n//2)

puiss(2,10)

Combien d'appels de la fonction ?

Complexité ?

Complexité en $O(\ln(n))$ : complexité logarithmique

Il y a $\left\lfloor\dfrac{\ln n}{\ln 2}\right\rfloor+2 \ $ appels de la fonction.

Exemple 3 : calcul de déterminants

Quelle est la complexité du calcul d'un déterminant d'ordre $n$, en utilisant la méthode du pivot de Gauss ?

Quelle est la complexité du calcul d'un déterminant d'ordre $n$, en développant $n-1$ fois par rapport à la 1ère colonne ?

Complexité du calcul d'un déterminant d'ordre $n$, en utilisant la méthode du pivot de Gauss :

$O(n^3)$

Complexité du calcul d'un déterminant d'ordre $n$, en développant $n-1$ fois par rapport à la 1ère colonne :

$O(n!)$

import numpy as np
import numpy.linalg as alg
import numpy.random as rd
from time import time
n=3
A=[]
for i in range(n):
    A.append([rd.randint(0,1000) for  j in range(n)])
B=np.array(A)

B

t1 = time()
print(alg.det(B))
t2 = time()
print("temps de calcul = ", t2 - t1, "secondes")

append ou + ?

L=[]
t1 = time()
for i in range(10000):
    L = L+[i]
t2 = time()

print("temps de calcul = ", t2 - t1, "secondes")

L=[]
t1 = time()
for i in range(10000):
    L.append(i)
t2 = time()

print("temps de calcul = ", t2 - t1, "secondes")