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)'.

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

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()

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()

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]

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

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()

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()

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 [ ]: