Análisis Informal del Tiempo de Ejecución
Introducido| English | Significado |
|---|---|
| run time/rʌn taɪm/ | tiempo de ejecución |
| linear/ˈlɪnɪə/ | lineal |
| quadratic/kwɒˈdrætɪk/ | cuadrática |
Contando el trabajo
- Medimos el tiempo de ejecución de un programa contando cuántas veces se ejecutan sus instrucciones clave.
- No en segundos (esos varían según la máquina), sino mediante un recuento de operaciones a medida que crece la entrada.
- Más operaciones para el mismo tamaño de entrada implican un algoritmo más lento.
- Esto nos permite comparar algoritmos de manera justa, independientemente del hardware.
Un bucle simple: aproximadamente n
- Un bucle sobre
nelementos ejecuta su cuerpo aproximadamentenveces. - Duplicar la entrada implica aproximadamente duplicar el trabajo. Esto es crecimiento lineal.
- Sumar un array, buscar en una lista elemento por elemento: todos requieren aproximadamente
npasos. - Se escribe informalmente como "orden
n".

Cómo crece el tiempo de ejecución con el número de elementos n
Un bucle anidado: aproximadamente n²
- Un bucle anidado sobre
nelementos ejecuta su cuerpo interno aproximadamenten × n = n²veces. - Duplicar la entrada implica aproximadamente cuatro veces el trabajo. Esto es crecimiento cuadrático.
- Comparar todos los pares, rellenar una cuadrícula de
n × n: aproximadamenten²pasos. n²crece mucho más rápido quencuandones grande.
Comparando el crecimiento
- Para comparar algoritmos, pregúntese cómo crece el trabajo a medida que crece la entrada.
- Para valores grandes de
n, un algoritmonsupera a unon²—y suele hacerlo por mucho—. - Enfóquese en la parte del código que más se ejecuta (generalmente el bucle más interno).
- El término de mayor crecimiento domina el tiempo de ejecución total.
Juzgue el tiempo de ejecución por CRECIMIENTO, no por un recuento fijo. Un algoritmo que realiza n pasos y otro que realiza 2n + 5 pasos ambos crecen linealmente —para efectos de comparación, la constante y el +5 no importan; lo que sí importa es la forma (n frente a n²). Un bucle simple equivale a n; un bucle anidado equivale a n², el cual crece mucho más rápido para entradas grandes.
Dos formas de encontrar duplicados en n elementos:
- Bucles anidados comparando cada par: aproximadamente
n²pasos. - Ordenar primero, luego una pasada: muchos menos pasos para valores grandes de
n. - Para
n = 1000,n²equivale a un millón de pasos —el enfoquen²es mucho más lento.
El análisis informal del tiempo de ejecución cuenta cuántas veces se ejecutan las sentencias a medida que crece la entrada. Un bucle simple sobre n elementos equivale a n (lineal); un bucle anidado equivale a n² (cuadrático), el cual crece mucho más rápido. Compare algoritmos por su crecimiento, centrándose en el código más ejecutado (el más interno).
Cómo crece el trabajo con n
Un bucle anidado (n²) crece mucho más rápido que un bucle simple (n).
Un bucle simple sobre n elementos ejecuta su cuerpo aproximadamente cuántas veces?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Un bucle sobre n elementos → aproximadamente n pasos (lineal).
Un bucle anidado sobre n elementos ejecuta su cuerpo interno aproximadamente cuántas veces?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
n × n = n² (cuadrático).
Para n = 1000, ¿cuántos pasos tiene aproximadamente un algoritmo n² (en millones)?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
1000² = 1,000,000 = 1 millón.
Para valores grandes de n, un algoritmo de n pasos es generalmente más rápido que uno de n² pasos.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
n² crece mucho más rápido, por lo que realiza mucho más trabajo en valores grandes de n.
Medimos el tiempo de ejecución en segundos, lo cual es igual en todas las computadoras.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Contamos operaciones frente al tamaño de la entrada; los segundos varían según la máquina.