Big-o: perché la complessità del tempo è di questi loop o (n)?
-
29-09-2020 - |
Domanda
Ho la seguente funzione.
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;
}
.
ha la complessità del tempo di O(N)
.Pensavo che sia O(N LogN)
(cioè se rimuovi il loop interno otteniamo)
for (int i = n; i > 0; i /= 2){
...
}
.
Questo è O(Log N)
non è vero?E il ciclo interno risulta essere O(N)
mentre aumenta semplicemente linearmente.Quindi penso che dovrebbe essere O(Log N * N)
.Cosa potrebbe andare storto sul mio pensiero?
Soluzione
Guarda quanti passi sta prendendo il loop interno.È $ n + \ frac {1} {2} n + \ frac {1} {4} n + \ cdots $ .Comunque Geometric Series ci dice:
$$ \ sum_ {k= 0} ^ {\ lceil \ log n \ rceil + c} \ frac {n} {2 ^ k}
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange