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
?