#

ne rien faire Last saved: Oct 29 10:49 AM

- File
- Edit
- View
- Insert
- Cell
- Kernel
- Help

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

. . .
Close Expand Open in Pager Close