Détermination de la complexité temporelle pour les segments de code

Question

Quelle est la complexité temporelle pour chacun des segments de code suivants?

1. int i, j, y=0, s=0; 
for (j = 1; j <= n; j ++) 
{ 
    y=y+j; 
} 
for (i = 1; i <= y; i ++) 
{ 
    s++; 
} 

Ma réponse est O (2n) car il fait passer dans chaque boucle n fois et il y a deux boucles

2. function (n) { 
    while (n > 1) { 
    n = n/3 ; 
} 

Ma réponse à celle-ci est n^(1/3) depuis n devient un tiers de sa taille à chaque fois que

3. function (n) { 
int i, j, k ; 
for (i = n/2; i <= n; i ++) { //n/2? 
    for (j = 1; j <= n; j = 2*j) { //logn 
    for (k = 1; k <= n; k = 2*k) { //logn 
     cout << ”COSC 2437.201, 301” << endl; 
    } 
    } 
} 
} 

J'ai dit la réponse à celui-ci était O (log2 * log2n * n/2) mais je suis assez confus au sujet de la première boucle. La boucle n'a qu'à parcourir la moitié de n fois, donc ce serait n/2 correct? Merci pour votre aide tout le monde.

Answer 1

Question 1

La première boucle est O(n), car il fonctionne n fois. Cependant, la seconde boucle est exécutée y fois, pas n - si la durée totale est « 2n »

A la fin de la première boucle, la valeur de y est:

Donc la deuxième boucle domine puisqu'elle est O(n^2), ce qui est donc aussi la complexité globale.

---

Question 3

Cette réponse est correcte (mais encore une fois, laissez tomber les facteurs de 2 dans la notation O). Cependant, vous devez faire attention à multiplier naïvement les complexités des boucles, car les limites des boucles internes peuvent dépendre des valeurs spontanées des boucles externes.

---

Question 2

C'est pasO(n^(1/3))! Votre raisonnement est incorrect.

Si vous regardez attentivement cette boucle, il est en fait similaire à la inverse des boucles internes en question 3:

• Au 3e trimestre la valeur de k commence à 1 et est multiplié par 2 à chaque fois jusqu'à ce qu'il atteigne n
• au 2ème trimestre la valeur de n est divisée par trois à chaque fois jusqu'à ce qu'il atteigne 1.

par conséquent, ils prennent les deux O(log n) étapes.

(Comme une note de côté, une boucle O(n^(1/3)) ressemblerait à quelque chose comme ça :)

for (int i = 1; i*i*i <= n; i++) 
    /* ... */