Relation de récurrence pour une boucle

Question

La question est de mettre en place une relation de récurrence pour trouver la valeur donnée par l'algorithme. La réponse devrait être en termes de teta().

foo = 0; 

for int i=1 to n do 
    for j=ceiling(sqrt(i)) to n do 
     for k=1 to ceiling(log(i+j)) do 
      foo++ 

Answer 1

Pas tout à fait sûr mais voilà. La deuxième boucle exécute 1 - sqrt(1) + 2 - sqrt(2) + ... + n - sqrt(n) = n(n+1)/2 - n^1.5 fois = O(n^2) fois. Voir here pour une discussion que sqrt(1) + ... + sqrt(n) = O(n^1.5).

Nous avons établi que la troisième boucle sera déclenchée O(n^2) fois. Ainsi, l'algorithme est asymptotiquement équivalent à quelque chose comme ceci:

for i = 1 to n do 
    for j = 1 to n do 
     for k = 1 to log(i+j) do 
      ++foo 

Cela conduit à la somme log(1+1) + log(1+2) + ... + log(1+n) + ... + log(n+n). log(1+1) + log(1+2) + ... + log(1+n) = log(2*3*...*(n+1)) = O(n log n). Cela est multiplié par n, résultant en O(n^2 log n).

Donc, votre algorithme est également O(n^2 log n), et aussi Theta(n^2 log n) si je ne me trompe pas.