Big-O :Pourquoi la complexité temporelle de ces boucles est-elle O(N) ?
-
29-09-2020 - |
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 ?
La solution
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$$
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange