Gran O:¿Por qué la complejidad temporal de estos bucles es O (N)?
-
29-09-2020 - |
Pregunta
Tengo la siguiente función.
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;
}
Tiene O(N)
complejidad del tiempo.Pensé que es O(N LogN)
(es decir.Si eliminamos el bucle interior obtenemos)
for (int i = n; i > 0; i /= 2){
...
}
Esto es O(Log N)
¿no es así?Y el bucle interior resulta ser O(N)
ya que simplemente aumenta linealmente.Así que creo que se supone que así es O(Log N * N)
.¿Qué podría salir mal en mi pensamiento?
Solución
Mira cuántos pasos está dando el bucle interior.Es $n + \frac{1}{2}n + \frac{1}{4}n + \cdots$.Sin embargo, el series geométricas Cuéntanos:
$$\sum_{k=0}^{\lceil\log n ceil +c}\frac{n}{2^k} < n\sum_{k=0}^\infty \frac{1}{2 ^k} = 2n$$
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange