Estaba leyendo another question y este código, sentí curiosidad:¿Por qué este código se considera O (N^6) en la notación Big Oh?
for(i = 0; i < n; i++)
{
for(j = 0; j < i*i; j++)
{
for(k = 0; k < i*j; k++)
{
pseudo_inner_count++;
for(l = 0; l < 10; l++);
}
}
}
No entiendo cómo esto puede ser O (N^6). ¿Alguien puede desglosarlo por mí?
En realidad es:
Los bucles están anidados, así que tenemos que multiplicarlos juntos (¿entiendes por qué?). El total es O (N) * O (N^2) * O (N^3) = O (N^6).
yo diría:
Quien haya votado en contra, explique por qué. – karlphillip
No he votado negativamente, pero no veo cómo el ciclo más interno puede ser O (n) cuando se ejecuta en tiempo constante, independientemente del valor de n. – antinome
Sí, esto se ve como O (N^5) para mí – bdares
Es
n para el primer bucle N $ ² $ para el segundo bucle N $ ³ $ para el tercer bucle
El bucle interior es O (1)
El total es O (N $ ⁶ $).
La razón por la cual el tercer ciclo es n³ es porque cuando lo piensas j alcanza n² y yo alcanzo n, entonces i * j alcanza n³.
Ok, entonces el resultado final se logra mediante una multiplicación de las evaluaciones de cada ciclo, y no a través de una suma (como se sugirió @Pascal). puede alguien más confirmar esto? – karlphillip
Pascal realmente no hizo la suma. Él multiplicó n * n^2 * n^2 * n y obtuvo n^6. Puede parecer una suma porque los exponentes se suman, pero así es como funcionan los exponentes en matemáticas. –
Esas votaciones ascendentes son confirma = D –