bonjour j'ai écrit ceci et je voudrais estimer le nombre d'opérations mais je ne sais pas quelles opérations compter
j'ai écrit auparavant un algorithme naïf où je compare des termes et je les intervertis si besoin, là je comptais le nombre d'interversions, $n^2/2$ environ au maximum
mais ici, je ne sais pas quoi compter
le nombre de tests ?
merci de vos éclaircissements
ps si vous avez des idées pour alléger le code je suis preneur
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#algorithme fusion pour trier une liste
#on prend [a,b,c...] de longueur 2**k, on appelle récursivement la fonction pour
#trier chaque moitié de liste.
# puis on tricote pour entremeler les deux sous listes dans l'ordre
 
u=0#tentative pour compter le nombre d'opérations mais que compter ?
from math import *#pour détecter si n=2**k
plus_inf=999999999#limite supérieure des listes
from random import *#pour shuffle
 
def tri_fusion(LL):
    global u
    #prend une liste de longueur 2**k
    n=len(LL)
    L=LL[:]
    psi=log(n)/log(2)
    bool=(psi!=int(psi))#teste si n≠2**k
    if (n==1):
        return(L)
    elif (bool):
        "erreur, n n'est pas puissance de 2"
    else:
        m=n//2
        (L1,L2)=(L[:m],L[m:])
        (L1,L2)=(tri_fusion(L1),tri_fusion(L2))
        L1.extend(m*[plus_inf])
        L2.extend(m*[plus_inf])
        L_tri=[]
        for _ in range(n):
            if (L1[0]<L2[0] and L1[0]!=plus_inf):
                L_tri.append(L1[0])
                del L1[0]
            elif (L1[0]>=L2[0] and L2[0]!=plus_inf):
                L_tri.append(L2[0])
                del L2[0]
        return(L_tri)
 
L=list(range(8))
for _ in range(10):
    shuffle(L)
    print(L,tri_fusion(L))