TEMPS D'EXÉCUTION

1 - Trois exemples


On va chronométrer le temps d'exécution des programmes. À l'aide d'un programme. Que voici.

from time import time as Maintenant
def Chronométrer(Programme, *Entrées) :
    début = Maintenant()
    Sortie = Programme(*Entrées)
    fin = Maintenant()
    return fin - début

Alors comment ça marche ? On regarde quelle heure il est, et on stocke l'information dans la variable début. Puis on exécute le programme, sur certaines entrées (le temps d'exécution dépend a priori des entrées auxquelles on applique le programme). On regarde à nouveau l'heure qu'il est, et on stocke l'information dans la variable fin. Dès lors la différence entre fin et début correspond au temps qui s'est écoulé pendant l'exécution du programme !

a) Temps exponentiel

?

def Fibonacci(n) :
    if n <= 1 :
        return n
    else :
        return Fibonacci(n - 1) + Fibonacci(n - 2)

b) Temps polynomial

?

def Occurrences(L, x) :
    nb = 0
    for l in L :
        if l == x :
            nb += 1
    return nb
def PlusOccurrent(L) :
    m = None ; occ_m = 0
    for l in L :
        o = Occurrences(L, l)
        if o > occ_m :
            m = l ; occ_m = o
    return m

?

def ?

c) Temps logarithmique

?

def PGCD(x, y) :
    x_ = abs(x) ; y_ = abs(y)
    while y_ > 0 :
        (x_, y_) = (y_, x_ % y_)
    return x_

d) Par rapport à quoi ?

?

def ?
?

def ?
?


2 - Observations empiriques et modélisation du temps d'exécution


?

def ?
?

def ?
?


3 - Temps moyen, coût des opérations usuelles


?

def ?
?

def ?
?