Discussion :

[redplayer]

Bonjour, un exercice me demande d'exprimer les valeurs "total" sous la forme d'une fonction de l'entrée n ainsi que de donner la complexité théorique en fonction du paramètre n avec la notation 0(..) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
def f1(n): 
    total = 0
    for i in range(0,n):
           total += 1
    for j in range(0,2*n):
           total += 1
    for k in range(0,3*n): 
           total += 1
    return total

Je trouve 6n avec une complexité de 0(n) c'est bien juste ?

deuxième exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
def f4(n):
       total =0
       i=1
       while i<n:
             i *=2
             total += 1
       return total

Je trouve la complexité 0(log2(n)) mais je ne parviens pas à exprimer le nombre d'instruction ...

Merci de votre aide !

[Franck_Cmr]

Salut, pour le dernier (f4(n)) la complexité est : O(ln(n)) et la valeur retournée total est : ln(n) / ln(2)
excuse moi, question peut-être indiscrète mais tu étudies dans quelle université ?

[redplayer]

merci pour la réponse ! pourquoi il y a cette division par ln(2) ?
Je suis à l'université de Fribourg comme vous

[Franck_Cmr]

ah hahahaha
euh car tu sais qu'on prend tous les n strictement plus petit que n, mais dans la boucle while, il y'a une deuxième condition.
Cette condition c'est le fait de multiplier i par 2, donc en gros ça va faire ( 1*2, ensuite 2*2, ensuite 4*2, ensuite 8*2...) donc imagine n c'est 20, bah en entrant dans la boucle while, i fera 8, ensuite ça fera 8*2, et ce sera strictement inférieur, si tu refais fois 2 on est déjà à 32
tout cela c'est pour te montrer que c'est pas i qui doit être plus petit que n (i <n) mais c'est plutôt i*2 qui doit être plus petit que n (i*2 < n)
Donc pour déterminer le nombre i pour que i*2 reste toujours plus petit que n, j'ai résolu l’équation 2^i = n ce qui fait ln(2*i) = ln(n), ce qui fait encore x(ln(2)) < ln(n), et finalement x < ln(x) / ln(2)
donc sur la ligne de la boucle While et pour les deux lignes à l'intérieur de la boucle, le nombre d’instructions est de "ln(x) / ln(2)" chacune.
j'ai beaucoup parlé mais j'espère que t'as capté