while

Question

envisager une boucle imbriquée:

for i from 1 to n 
    k=i; 
    while(k>0) 
    do c operations; 
    k=floor[k/2]; 
    end while 
end for 

pour calculer num des opérations j'ai besoin de savoir combien d'itérations dans la boucle while d'abord, je me suis dit que (probablement faux): k = i, k = plancher [1/2 * i], k = plancher [1/4] .... k = plancher [(1/2)^j * i], k = 1. Je sais que le dernier k sera toujours 1 bon? et le nombre d'opérations dans la boucle while est j + 1? et je ne sais pas comment résoudre j. Quelqu'un peut-il aider?

Answer 1

alors que la boucle boucle pour les temps log (i). donc à l'intérieur d'une itération de la boucle for i, les opérations c * log (i) sont effectuées. donc au total:

c * log (1) + c * log (2) + c * log (3) + ... + c * log (n)

Si vous avez besoin le moteur d'exécution asymptotique : c'est O (n log (n)).