Informal Run-Time Analysis · Análisis Informal del Tiempo de Ejecución
| English | Español |
|---|---|
| run time/rʌn taɪm/ | tiempo de ejecución |
| linear/ˈlɪnɪə/ | lineal |
| quadratic/kwɒˈdrætɪk/ | cuadrática |
Counting the work
- We measure a program's run time 运行时间 by how many times its key statements run.
- Not seconds (those vary by machine) — a count of operations as the input grows.
- More operations for the same input size → slower algorithm.
- This lets us compare algorithms fairly, independent of hardware.
Contando el trabajo
- Medimos el tiempo de ejecución 运行时间 de un programa contando cuántas veces se ejecutan sus sentencias 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.
A single loop: about n
- A loop over
nitems runs its body aboutntimes. - Double the input → about double the work. This is linear 线性 growth.
- Summing an array, searching a list one-by-one: all about
nsteps. - Written informally as "order
n."
Un bucle simple: aproximadamente n
- Un bucle sobre
nelementos ejecuta su cuerpo aproximadamentenveces. - Duplicar la entrada implica aproximadamente duplicar el trabajo. Este es un crecimiento lineal 线性.
- Sumar un array, buscar en una lista elemento por elemento: todos requieren aproximadamente
npasos. - Se escribe informalmente como "orden
n".
A nested loop: about n²
- A nested loop over
nitems runs its inner body aboutn × n = n²times. - Double the input → about four times the work. This is quadratic 二次 growth.
- Comparing all pairs, filling an
n × ngrid: aboutn²steps. n²grows much faster thannasngets large.
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. Este es un 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.
Comparing growth
- To compare algorithms, ask how the work grows as the input grows.
- For large
n, annalgorithm beats ann²algorithm — often by a lot. - Focus on the part of the code that runs the most (usually the innermost loop).
- The fastest-growing term dominates the total run time.
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.
Judge run time by GROWTH, not a fixed count. An algorithm that does n steps and one that does 2n + 5 steps both grow linearly — for comparing, the constant and the +5 don't matter; the shape (n vs n²) does. A single loop is about n; a nested loop is about n², which grows far faster for large inputs.
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.
Two ways to find duplicates in n items:
- Nested loops comparing every pair: about
n²steps. - Sort first, then one pass: far fewer steps for large
n. - For
n = 1000,n²is a million steps — then²approach is much slower.
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.
Informal run-time analysis counts how many times statements run as the input grows. A single loop over n items is about n (linear); a nested loop is about n² (quadratic), which grows much faster. Compare algorithms by their growth, focusing on the most-executed (innermost) code.
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).
How the work grows with n · Cómo crece el trabajo con n
A nested loop (n²) grows far faster than a single loop (n). · Un bucle anidado (n²) crece mucho más rápido que un bucle simple (n).
A single loop over n items runs its body about how many times? · Un bucle simple sobre n elementos ejecuta su cuerpo aproximadamente cuántas veces?
One loop over n items → about n steps (linear). · Un bucle sobre n elementos → aproximadamente n pasos (lineal).
A nested loop over n items runs its inner body about how many times? · Un bucle anidado sobre n elementos ejecuta su cuerpo interno aproximadamente cuántas veces?
n × n = n² (quadratic). · n × n = n² (cuadrático).
For n = 1000, about how many steps is an n² algorithm (in millions)? · Para n = 1000, ¿cuántos pasos tiene aproximadamente un algoritmo n² (en millones)?
1000² = 1,000,000 = 1 million. · 1000² = 1,000,000 = 1 millón.
For large n, an n-step algorithm is generally faster than an n²-step one. · Para valores grandes de n, un algoritmo de n pasos es generalmente más rápido que uno de n² pasos.
n² grows much faster, so it does far more work at large n. · n² crece mucho más rápido, por lo que realiza mucho más trabajo en valores grandes de n.
We measure run time in seconds, which is the same on every computer. · Medimos el tiempo de ejecución en segundos, lo cual es igual en todas las computadoras.
We count operations vs. input size — seconds vary by machine. · Contamos operaciones frente al tamaño de la entrada; los segundos varían según la máquina.