¿Los bucles anidados siempre son O (n ^ k)?

Si tengo un ciclo dentro de otro ciclo, pero sé que el ciclo interno solo se ejecutará una vez, ¿este algoritmo seguirá siendo O (n ^ 2)?

For i = 1 to n do

     For j = 1 to i do

          If (i==j) do

              For k = 1 to n

                  {Do stuff}

El ciclo muy interno se ejecutará como máximo 1 vez, ya ique solo será igual juna vez por iteración del segundo ciclo. ¿Sigue siendo n ^ 3?

algorithms Juan
fuente

Respuestas:

Piénsalo de esta manera. Independientemente de N, la función más interna solo se ejecutará una vez por ejecución del segundo bucle. Es decir, la cantidad de veces que se ejecuta depende de N linealmente. Esto significa que puede tratar todo dentro del primer bucle como una operación de tiempo lineal (O (n)) (suponiendo que {do stuff} también es tiempo constante). Si considera el bucle más externo, verá que hace algo que requiere O (n), n veces. Esto significa que el tiempo de ejecución general es O (n ^ 2)

Si duplica N, habrá un total de N ^ 2 iteraciones adicionales. Por lo tanto, el tiempo de ejecución general es N ^ 2.

Oleksi
fuente

¡Muchas gracias! Esto es lo que creía, sin embargo, la forma en que siempre he pensado en los bucles anidados me confundió

John

@john, no hay problema. Es complicado acertar. Ayuda si piensa duplicar el N y luego pregunta cómo afecta la cantidad de veces que hace algo.

Oleksi

¿Eh? El primer y TERCER bucle dependen de n. El condicional solo es verdadero una vez por ejecución del segundo bucle. Aquí tenemos dos tareas n ^ 2, el par de bucles ij y el par de bucles ik. Sin embargo, el resultado sigue siendo n ^ 2.

Loren Pechtel

@LorenPechtel whoops. Lo siento. Pasé por alto esto. Actualicé la respuesta para reflejar esto.

Oleksi

No, los bucles anidados no significan automáticamente que su algoritmo sea O (n ^ k). La unidad básica de trabajo en su ejemplo es {Do stuff}, por lo que debe contar cuántas veces se ejecutará a medida que naumente. Ni siquiera necesita el jbucle, ya que solo cuenta desde 1 hasta iy no hace nada hasta que llega i. Solo en esa iteración realmente funciona, por lo que su código de ejemplo es O (n ^ 2).

Bill el lagarto
fuente