In [1]:
%pylab inline
Welcome to pylab, a matplotlib-based Python environment [backend: module://IPython.zmq.pylab.backend_inline]. For more information, type 'help(pylab)'.
. . .
x
Le triangle
In [2]:
def triangle(n):
for i in range(n):
for j in range(i,n):
pass
. . .
In [3]:
import time
def temps(f,L):
tps=[]# contiendra une liste de temps de calcul
for j in L:
start = time.time()
f(j)
dureeCalcul=time.time() - start # dureeCalcul=temps de calcul de f(j)
tps.append(dureeCalcul)
return tps
. . .
x
Le triangle : complexité expérimentale par le temps
In [4]:
X=range(100,20000,500)
Yt=temps(triangle,X)
pos=20
Ys=[x*(x+1)*Yt[pos]/(X[pos]*(1+X[pos])) for x in X]
axis([min(X),max(X),min(Yt),max(Yt)])
plot(X,Yt,'r--',X,Ys,'b:')
ylabel('duree')
xlabel('valeur de n')
show()
. . .
x
Le triangle : complexité expérimentale par compteur
In [5]:
def triangleOp(n):
cpt=0
for i in range(n):
for j in range(i,n):
cpt+=1
return cpt
. . .
In [6]:
Yop=[triangleOp(x) for x in X]
Yopg=[y*Yt[pos]/Yop[pos] for y in Yop]
plot(X,Yt,'r--',X,Yopg,'b:')
show()
. . .
x
Le tri par sélection du minimum
In [7]:
def triselection(L):
n=len(L)
for i in range(n-1):
mini,indice_mini=L[i],i
for j in range(i,n):
if mini>L[j] : mini,indice_mini=L[j],j
L[i],L[indice_mini]=mini,L[i]
. . .
In [8]:
L=[5,8,1,45,2,3,1,7,2]
triselection(L)
print L
[1, 1, 2, 2, 3, 5, 7, 8, 45]
. . .
x
L'arbre
In [9]:
def arbre(n) :
h,t=1,n
while t>=1 :
for j in range(h):
for k in range(t):
pass
h*=2
t/=2
. . .
x
Durée de vie de mon arbre
In [10]:
def duree(f,n):
start = time.time()
f(n)
tps=time.time() - start
return tps
X=[2**k for k in range(13,23)]
Ya=[duree(arbre,x) for x in X]
d=8
Yb=[x*math.log(x)*Ya[d]/(X[d]*math.log(X[d])) for x in X]
axis([min(X),max(X),min(Yb),max(Yb)])
plot(X,Ya,'b--',X,Yb,'r:')
ylabel('duree')
xlabel('valeur de n')
show()
. . .
x
Complexité expérimentale par compteur
In [11]:
def arbreOp(n) :
cpt=0
h,t=1,n
while t>=1 :
for j in range(h):
for k in range(t):
cpt+=1
h*=2
t/=2
return cpt
. . .
In [18]:
Yop=[arbreOp(x) for x in X]
Yopp=[(1.0*y)/Yop[d]*Ya[d] for y in Yop]
plot(X,Ya,'r--',X,Yopp,'b:')
show()
. . .
x
Une programmation du tri fusion
In [19]:
def fusion(A,B,C,a=0,b=0):
if a<len(A) and b<len(B):
if A[a]<B[b]:
C.append(A[a])
return fusion(A,B,C,a+1,b)
else :
C.append(B[b])
return fusion(A,B,C,a,b+1)
else : return C+A[a:]+B[b:]
def tri_fusion(L):
if len(L)<2:
return L
else :
m=len(L)//2
return fusion(tri_fusion(L[:m]),tri_fusion(L[m:]),[])
print tri_fusion([5,8,1,3,45,2,7])
[1, 2, 3, 5, 7, 8, 45]
. . .
In [ ]:
. . .