2011-07-21 19 views

Respuesta

14

En realidad es:

  • El ciclo i repite O (N) veces, por lo que el valor de i es O (N), por lo que podemos decir O (I) = O (N).
  • El bucle j itera O (I^2) = O (N^2) veces (cuando se considera por sí solo, sin el bucle externo).
  • El ciclo k itera O (I * J) = O (N * N^2) = O (N^3) veces.
  • El ciclo l solo itera 10 veces, por lo que es O (1).

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).

+0

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

+2

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. –

+0

Esas votaciones ascendentes son confirma = D –

-1

yo diría:

  • n para el primer bucle
  • N $ ² $ para el segundo bucle => total de N $ ³ $
  • N $ ² $ para el bucle tercero => total de n⁵
  • otro n-loop => total de N $ ⁶ $
+0

Quien haya votado en contra, explique por qué. – karlphillip

+4

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

+0

Sí, esto se ve como O (N^5) para mí – bdares

1

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³.

Cuestiones relacionadas