aide à la complexité de trouver de cet algorithme

Question

je tente de trouver la complexité de cet algorithme:

m=0; 
i=1; 
while (i<=n) 
{ 
    i=i*2; 
    for (j=1;j<=(long int)(log10(i)/log10(2));j++) 
    for (k=1;k<=j;k++) 
      m++; 
} 

Je pense qu'il est O (log (n) * log (log (n)) * log (log (n))):

• la boucle 'i' se déroule jusqu'au i = log (n)
• la boucle 'j' se déroule jusqu'au log (i) un moyen log (log (n))
• la La boucle 'k' court jusqu'à k = j -> k = log (i) -> k = log (log (n))

donc O (log (n) * log (log (n)) * log (log (n))).

Answer 1

La complexité temporelle est Theta (log (n)^3).

Soit T = étage (log_2 (n)). Votre code peut être réécrit comme:

int m = 0; 
    for (int i = 0; i <= T; i++) 
    for (int j = 1; j <= i+1; j++) 
    for (int k = 1; k <= j; k++) 
    m++; 

Ce qui est évidemment Theta (T^3).

Modifier: Voici une étape intermédiaire pour réécrire votre code. Soit a = log_2 (i). un est toujours un entier parce que i est une puissance de 2. Ensuite, votre code est clairement équivalent à:

m=0; 
a=0; 
while (a<=log_2(n)) 
{ 
    a+=1; 
    for (j=1;j<=a;j++) 
    for (k=1;k<=j;k++) 
      m++; 
} 

Les autres changements que je ne devais nommer étage (log_2 (n)) que T, un i comme, et en utilisant une boucle for au lieu d'un moment.

J'espère que c'est clair maintenant.

Answer 2

Est-ce que ce travail est fait?

Quelques conseils:

Je ne sais pas si le code est en train de faire ce qu'il devrait être. log10 renvoie une valeur flottante et la distribution à (long int) va probablement couper de .9999999999. Je ne pense pas que cela soit voulu. La ligne devrait peut-être ressembler à ce que:

for (j=1;j<=(long int)(log10(i)/log10(2)+0.5);j++) 

Dans ce cas, vous pouvez réécrire ce que:

m=0; 
for (i=1, a=1; i<=n; i=i*2, a++) 
    for (j=1; j<=a; j++) 
     for (k=1; k<=j; k++) 
      m++; 

Par conséquent, votre hypothèse de la complexité de la « j'- et » k'-boucle est faux.
(la boucle externe exécute log n fois, mais i augmente jusqu'à n, pas log n)