¿Cuál es la complejidad de:complejidad de cálculo
int f4(int n)
{
int i, j, k=1, count = 0;
for(i = 0; i < n; i++)
{
k *= 3;
for(j = k; j; j /= 2)
count++;
}
return count;
}
Sé que es O (n^2), pero ¿cómo se calcula esto? y por qué no es n * log n?
Hay n bucles externos. En cualquier punto, k = 3i. Hay log2(k) bucles internos (ya que reducir a la mitad j en cada iteración.)
log2(3i) = log3 (3i)/log3(2) = i/(constant)
lo tanto la complejidad del bucle interno es i. En otras palabras, este programa tiene la misma complejidad (pero no exactamente el mismo número de iteraciones) como
int f4changed(int n)
{
int i, j, count = 0;
for(i = 0; i < n; i++)
{
for(j = 0; j < i; j++)
{
count++;
}
}
}
Ésta es O(n2)as you've already seen.
OK, muchas gracias! – yyy
¿Puedo sugerir escribir '3 i' para la potencia, para evitar cualquier posible confusión con bit_xor? –
Hecho, gracias Hosam. –
i = 1 resultados en 3 iteraciones (del bucle interior) (3, 1, 0)
i = 2 es 8 (5 a continuación, 3)
i = 3 es 13 (7 + 5 + 3)
Lo que tiene está aproximándose a arithmetic series, que es O (n).
Para completar (y para explicar por qué el número exacto de iteraciones no importa), consulte Plain english explanation of Big O (esto es más para otros lectores que usted, el póster ya que parece saber qué sucede).
La complejidad de Log (Pow (3, n)) ~ O (N). Si el ciclo interno era k * = 2, entonces el número de iteraciones también habría sido n.
Para calcular O (~) se usa el término de mayor potencia y los demás se descuidan. Log (Pow (3, n)) puede estar limitado como:
Log (Pow (2, n)) < = Registro (Pow (3, n)) < = Registro (Pow (4, n))
Ahora Log (Pow (4, n)) = 2 * Log (Pow (2, n)).
El término de mayor potencia aquí es n (ya que 2 es una constante).
Después de haber examinado sus otras preguntas, parece que solo está tratando de hacer su tarea actual ... Buena suerte con eso :-) – scraimer
Estoy buscando respuestas a algunas preguntas sobre HW que no soy Seguro de cómo resolverlo solo, pero no estoy tratando de hacer todo por otros. Solo trato de entender cómo funciona la complejidad. – yyy
Corman Leisterson Rivest y Stein. El gran libro blanco. Pídalo por su nombre. –