int num = n/4;
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
int count = 1;
}
}
}
Según los libros que he leído, este código debería ser O ((n^3)/4). Pero aparentemente no es así. para encontrar el Big-O para bucles anidados se supone que debes multiplicar los límites? Entonces este debe ser num * n * n o n/4 * n * n.¿Encontrando Big-O con múltiples bucles anidados?
O((n^3)/4) no tiene sentido en términos de notación de O grande, ya que está destinado a medir la complejidad como una proporción del argumento. Dividir por 4 no tiene ningún efecto ya que eso cambia el valor de la razón pero no su naturaleza.
Todos estos son equivalentes:
O(n^3)
O(n^3/4)
O(n^3*1e6)
Otros términos sólo tienen sentido cuando incluyen un término n, tales como:
O(n^3/log(n))
O(n^3 * 10^n)
Como Anthony Kanago señala con razón, que es la convención a:
O(n^2+n) = O(n^2) .O(n^2/4) = O(n^2).Como nota aparte, no siempre estoy de acuerdo con esa primera regla en todos los casos. Es una buena regla para decidir la tasa máxima de crecimiento de una función, pero para cosas como la comparación de algoritmos (a) donde puedes poner un límite al parámetro de entrada, algo como O(n^4+n^3+n^2+n) es notablemente peor que O(n^4).
En ese caso, se debe incluir cualquier término que dependa del parámetro de entrada. De hecho, incluso los términos constantes pueden ser útiles allí. Compare por ejemplo O(n+1e100) contra O(n^2) - este último superará al primero durante bastante tiempo, hasta que n sea lo suficientemente grande como para tener un efecto sobre el término constante.
(a) Hay, por supuesto, aquellos que dicen que no se debe utilizar en una forma tal, sino el pragmatismo menudo supera el dogmatismo en el mundo real :-)
Además, n^3 + n incluye ese '+ n' como un término de orden inferior que se puede descartar. – Anthony
Gracias, @Anthony, estaba preparando algunas muestras, debería haberlas leído un poco más cuidadosamente antes de publicarlas. – paxdiablo
Esto es cierto solo si su apellido no es "Knuth" –
De http://en.wikipedia.org/wiki/Big_O_notation puede ver que las constantes como 1/4 no juegan un papel para determinar la notación Big-O. El único hecho interesante es que es n^3, por lo tanto O (N^3).
Un pequeño tecnicismo. La notación Big O tiene la intención de describir la complejidad en términos del 'tamaño' de la entrada, no el valor numérico. Si su entrada es un número, entonces el tamaño de la entrada es el número de dígitos de su número. Por desgracia, su algoritmo es O (2^N^3) con N es la cantidad de dígitos.
Me has perdido aquí, @token. El "tamaño" en este ciclo es claramente el valor numérico, no el número de dígitos (lo que requeriría una base de registro-10 en n en algún lugar). – paxdiablo
Formalmente, la complejidad del tiempo se pueden deducir como la siguiente:
n/4 * n * n = (n^3)/4 –
Un compilador inteligente sería probablemente optimice este nido de bucle para que sea O (1), ya que en realidad no hace nada. – tgamblin
Un compilador "inteligente" lo dejaría solo a menos que se indique lo contrario: puede ser un ciclo de tiempo en un sistema integrado que controla el flujo sanguíneo a través de una máquina de diálisis :-) – paxdiablo