Aquí hay un desglose de los escenarios comunes y sus complejidades de tiempo de ejecución:
1. Tiempo constante (o (1))
* Cuando el bucle ejecuta un número fijo y pequeño de veces, independientemente del tamaño de entrada. Esto es raro, pero podría suceder si la condición de bucle depende de un valor constante y no se ve afectado por la entrada.
`` `Python
i =0
Mientras i <5:# buce exactamente 5 veces
Imprimir (i)
i +=1
`` `` ``
2. Tiempo logarítmico (O (log n))
* Cuando el bucle reduce el tamaño del problema por un factor constante en cada iteración. Un ejemplo clásico es la búsqueda binaria.
`` `Python
bajo =0
alto =n - 1
Mientras que bajo <=High:# Loop continúa mientras exista el espacio de búsqueda
Mid =(bajo + alto) // 2
Si arr [Mid]
Elif arr [Mid]> objetivo:
Alto =Mid - 1
demás:
¡Return Mid # objetivo encontrado!
`` `` ``
Aquí, el tamaño del espacio de búsqueda (de `bajo` a` alto ') se reduce a la mitad en cada iteración. Por lo tanto, el bucle se ejecuta aproximadamente `log2 (n)` veces.
3. Tiempo lineal (o (n))
* Cuando el bucle itera a través de cada elemento de una entrada de tamaño `n` una vez. Esto es muy común.
`` `Python
i =0
mientras que yo
i +=1
`` `` ``
En este caso, el cuerpo del bucle ejecuta `n 'veces.
4. Tiempo cuadrático (o (n^2))
* Cuando el bucle itera `n` tiempos para cada uno de los elementos` n` (a menudo bucles anidados).
`` `Python
i =0
Mientras yo
Mientras que J
j +=1
i +=1
`` `` ``
Esto implica un bucle `while` anidado, donde ambos bucles iteran` n` veces. El número total de iteraciones es `n * n =n^2`.
5. Otro tiempo polinomial (o (n^k))
* Generalizaciones del ejemplo cuadrático anterior. Por ejemplo, tres bucles anidados que cada uno iterate `n 'tiempos daría como resultado una complejidad O (n^3).
6. Tiempo exponencial (o (2^n)) o peor
* El tiempo de ejecución del bucle crece exponencialmente con el tamaño de entrada. Esto a menudo indica un algoritmo mal diseñado o un problema inherentemente muy difícil. Los ejemplos pueden implicar probar todas las combinaciones posibles de elementos.
Consideraciones clave:
* Tamaño de entrada (n): ¿Qué representa `n '? El tamaño de una matriz, la magnitud de un número, etc. Esto es crítico para expresar la complejidad en términos de entrada.
* Cambios de variable de condición: ¿Cómo cambia las variables (s) de la condición de bucle dentro del bucle? ¿Aumenta en una cantidad constante, disminuye por un factor, etc.?
* Operaciones dentro del bucle: El tiempo de ejecución de las operaciones * Inside * el bucle importa. Si, por ejemplo, tiene una operación O (n) dentro de un bucle que se ejecuta n veces, la complejidad general es o (n * n) =o (n^2).
Cómo determinar la complejidad del tiempo de ejecución:
1. Identifique el tamaño de entrada (n): ¿Cuál es el parámetro de tamaño relevante?
2. Determine el número de iteraciones: ¿Cuántas veces se ejecuta el bucle *en relación con `n` *? Esta es la parte central.
3. Considere las operaciones dentro del bucle: Si el bucle contiene operaciones complejas, se debe tener en cuenta su complejidad en tiempo de ejecución. La complejidad general se convierte en la complejidad de las iteraciones de bucle multiplicadas por la complejidad de la operación más costosa dentro del bucle.
4. Expresa la complejidad: Use la notación Big O (O (), ω (), θ ()) para representar el límite superior, un límite inferior o un límite apretado del tiempo de ejecución. Por lo general, nos centramos en Big O (peor de los casos).
Ejemplo:
`` `Python
Def process_array (arr):
n =len (arr)
i =0
Mientras yo
Mientras J
arr [i], arr [j] =arr [j], arr [i] # Swap de tiempo constante
j +=1
i +=1
regresar arr
`` `` ``
Análisis:
* `n` es la longitud de la matriz de entrada` arrr`.
* El bucle exterior (`i`) ejecuta` n` veces.
* El bucle interno (`j`) funciona aproximadamente 'n - i` veces. En el peor de los casos, cuando `i` es 0, se ejecuta` n` veces.
* La operación de intercambio dentro del bucle interno es o (1).
Por lo tanto, los bucles anidados contribuyen a la complejidad O (n^2). El intercambio es de tiempo constante y no afecta el tiempo de ejecución general de O (N^2). Este algoritmo es similar al tipo de selección.
En resumen, para determinar la complejidad del tiempo de ejecución de un bucle `while`, analice cuidadosamente cuántas veces el bucle se ejecuta en relación con el tamaño de entrada y considere la complejidad de las operaciones realizadas dentro del bucle.