Big-O :Pourquoi la complexité temporelle de ces boucles est-elle O(N) ?

Question

J'ai la fonction suivante.

int fun(int n) 
{ 
  int count = 0; 
  for (int i = n; i > 0; i /= 2) 
     for (int j = 0; j < i; j++) 
        count += 1; 
  return count; 
} 

Il a O(N) complexité temporelle.Je pensais que c'était O(N LogN)(c'est à dire.Si nous supprimons la boucle interne, nous obtenons)

for (int i = n; i > 0; i /= 2){
...
}

C'est O(Log N) n'est-ce pas ?Et la boucle intérieure s'avère être O(N) car il augmente simplement de manière linéaire.Donc je pense que c'est censé être O(Log N * N).Qu'est-ce qui pourrait mal se passer dans ma pensée ?

Answer 1

Regardez combien d’étapes fait la boucle interne.C'est $n + \frac{1}{2}n + \frac{1}{4}n + \cdots$.Cependant, le série géométrique nous dit:

$$\sum_{k=0}^{\lceil\log n ceil +c}\frac{n}{2^k} < n\sum_{k=0}^\infty \frac{1}{2 ^k} = 2n$$