Este mapa explica cómo se calcula el coste de un algoritmo: cuántas operaciones hace en función del tamaño de los datos, n, y cómo crece cuando n crece.
El coste es una función de n. Los segundos dependen del ordenador; las operaciones, no.
Pulsa cada recuadro para ver su explicación. Las flechas ← → (o los botones del pie) pasan a la siguiente y Esc la cierra. Cuando ya lo has visto, aparece un ✓; pulsa para quitarlo. Los recuadros con «?» son de otros niveles.
Este mapa explica cómo se calcula el coste de un algoritmo: cuántas operaciones hace un programa. Cada recuadro tiene una explicación corta y, en algunos casos, un ejercicio.
Un algoritmo es más rápido cuando hace menos operaciones.
Pulsa cada recuadro para ver su explicación. Las flechas ← → pasan a la siguiente y Esc la cierra. Cuando ya lo has visto, aparece un ✓.
4.º ESO (para aventajados). Versión simplificada: reglas de cálculo, orden respecto a n y búsqueda dicotómica. Sin notación O(·) formal, sin gráficas de los algoritmos y sin el recuadro de operaciones.
Encaja en: Digitalización 4.º (pensamiento computacional: criterios 3.1 y 3.2, algoritmos lógicos y eficientes).
Actividad sugerida: contar las operaciones de un bucle y después comprobar con la búsqueda dicotómica cuántos pasos hace.
PTD-I · 1.º de Bachillerato. Se añaden las reglas de cálculo (secuencia, condicional y bucle), la notación O(·), las gráficas de crecimiento y de tiempo, la búsqueda lineal y la ordenación por selección. Los experimentos de tiempo (ms) dejan de ser el centro: lo que se mide es el número de operaciones.
Encaja en: Programación y Tratamiento de Datos I: CEsp1 (análisis y diseño de algoritmos, criterio 1.3 sobre el coste computacional) y CEsp3 (eficiencia y complejidad de las operaciones en estructuras de datos).
Actividad sugerida: con 10⁹ operaciones por segundo y n = 10⁶, calcular cuánto tardarían la búsqueda lineal (n) y la burbuja (n(n−1)/2), y compararlo con la gráfica de tiempo.
PTD-II · 2.º de Bachillerato. Mismo contenido que PTD-I: reglas de cálculo, notación O(·), gráficas de crecimiento y los algoritmos de búsqueda y ordenación.
Encaja en: Programación y Tratamiento de Datos II: CEsp1 (algoritmos y pensamiento computacional).
Actividad sugerida: comparar a mano la búsqueda lineal y la dicotómica con n = 1 000 000 y justificar la diferencia.
Los recuadros con «?» están ocultos en este nivel: un clic los descubre y muestra su relación, otro abre la ventana y, después de verla, otro clic los vuelve a ocultar. El botón 🔗 copia un enlace con el nivel y los recuadros descubiertos.
El selector Nivel cambia el mapa y todas las ventanas. En la dirección se guardan el nivel (?edad=4eso, ptd1 o ptd2) y los recuadros descubiertos (&ver=casos,fonts).
Cuando decimos que un algoritmo es rápido, hay que decir rápido en qué. Los segundos dependen del ordenador, del sistema y de lo que se esté ejecutando. Por eso contamos operaciones.
Cuando compares dos algoritmos, pregúntate: qué crece y cuánto?
El coste computacional mide el trabajo que hace un programa según el tamaño de los datos (n. Mira dos cosas: el tiempo (número de operaciones) y la memoria (cuánto espacio ocupa).
El coste computacional de un algoritmo es el número deoperaciones elementales que hace, en función del tamaño de los datos, n. Los segundos dependen del ordenador; las operaciones, no.
Una operación elemental (asignación, suma, comparación o acceso a una posición) cuesta 1. Se cuenta el peor caso, que es lo que garantiza el resultado para cualquier dato.
| Función T(n) | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| n | 10 | 1 000 | 1 000 000 |
| n² | 100 | 1 000 000 | 1 000 000 000 000 |
Los segundos no sirven para comparar algoritmos. Cuenta operaciones y mira cómo crecen cuando crece n.
El tamaño n. Todas las fórmulas dependen de un tamaño, n: el número de datos que recibe el algoritmo. Define n antes de contar (número de elementos, de dígitos o de filas, según el problema).
Un programa hace instrucciones una tras otra. Para calcular el coste, suma las instrucciones. Si hay un bucle, multiplica por el número de veces que se repite.
Una instrucción simple cuesta 1. Un bucle multiplica el coste de su cuerpo por el número de repeticiones.
Un programa combina cuatro estructuras. El coste total se calcula aplicando una regla a cada una.
| Estructura | Regla de coste | Ejemplo |
|---|---|---|
| Instrucción simple | 1 | x ← x + 1 → 1 |
| Secuencia | suma de los costes | A; después B → T(A) + T(B) |
| Condicional | test + el camino más caro | si … entonces … si no … → 1 + máximo(T₁, T₂) |
| Bucle | iteraciones × coste del cuerpo | para i de 1 a n: x ← x + 1 → n |
Cuando no sabes qué camino de un condicional se ejecutará, usa el más caro: es el peor caso.
El coste de un bucle es el coste de su cuerpo multiplicado por el número de repeticiones. Una operación no se nota; un millón, sí.
| Estructura | Operaciones con n = 1 000 | Operaciones con n = 1 000 000 |
|---|---|---|
| Un bucle | 1 000 | 1 000 000 |
| Dos bucles anidados | 1 000 000 | 1 000 000 000 000 |
Cuenta cuántas veces se ejecuta el cuerpo más interno. Un bucle de n pasos hace n operaciones; dos bucles anidados de n pasos hacen n · n.
Dos bucles anidados son O(n²); un bucle, O(n).
Una estructura que parece sencilla («solo es un bucle») puede esconder una búsqueda dentro. Mira siempre qué hay dentro del bucle.
Un bucle repite su cuerpo. El coste total es el coste del cuerpo multiplicado por el número de repeticiones.
| Estructura | Operaciones con n = 1 000 | Operaciones con n = 1 000 000 |
|---|---|---|
| Un bucle | 1 000 | 1 000 000 |
| Dos bucles anidados (n · n) | 1 000 000 | 1 000 000 000 000 |
| Dos bucles, el segundo hasta i | 500 500 | 500 000 500 000 |
Un bucle es O(n). Dos bucles anidados son O(n²). Los bucles anidados que llegan hasta i hacen n(n+1)/2 pasos: también O(n²), porque ignoramos la constante ½.
Una estructura que parece sencilla («solo es un bucle») puede esconder una búsqueda dentro. Mira siempre qué hay dentro del bucle.
La burbuja compara vecinos y los intercambia si están en orden incorrecto. Repite pasadas hasta que no hace ningún intercambio. Es el algoritmo típico para entender el coste, porque se puede contar todo.
| n (datos) | Comparaciones (peor caso) | Intercambios (media) |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
Cada pasada sitúa el valor más grande al final. Con n datos, la primera pasada hace n−1 comparaciones, la siguiente n−2, y así hasta 1. En total, en el peor caso: n(n−1)/2.
Fíjate: si multiplicas los datos por 10, el trabajo se multiplica por 100.
Esto es O(n²). Las comparaciones crecen como el cuadrado de n.
La burbuja compara cada pareja de vecinos y intercambia los que están desordenados. Después de cada pasada, el valor más grande queda al final.
| n (datos) | Comparaciones (peor caso) | Intercambios (media) |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
La primera pasada hace n−1 comparaciones, la segunda n−2, y así hasta 1. Total en el peor caso: (n−1) + (n−2) + … + 1 = n(n−1)/2, es decir O(n²).
Gráfica de tiempo: el tiempo es proporcional al número de operaciones. Con 10⁹ operaciones por segundo, 10⁶ operaciones tardan 1 ms.
Si la lista está ordenada, no hace falta mirarla toda. Miras el medio y descartas la mitad que no puede contener lo que buscas. Cada paso reduce el tamaño a la mitad.
La lista es 1, 2, 3… n: no hace falta guardarla toda en memoria, por eso se puede probar con 1 000 000 000.
| n (datos) | Pasos dicotómica (peor caso) | Comparaciones lineal (peor caso) |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
Cada paso hace una comparación y elimina la mitad. Los pasos son aproximadamente log₂ n. Por eso 1 000 000 000 de datos solo necesitan 30 pasos.
Esto es O(log n).
La dicotómica solo funciona si la lista está ordenada. Ordenarla también tiene un coste.
La búsqueda dicotómica mira el medio de la lista ordenada y descarta la mitad que no puede contener lo que buscas. Cada paso divide entre 2.
La lista es 1, 2, 3… n. Solo se cuentan los pasos: no hace falta guardarla en memoria.
| n (datos) | Pasos (peor caso) | Búsqueda lineal (peor caso) |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
Cada paso reduce el tamaño a la mitad: después de k pasos quedan n / 2ᵏ elementos. Como n / 2ᵏ = 1 cuando k = log₂ n, el coste es O(log n).
La búsqueda dicotómica solo funciona si la lista está ordenada. Ordenarla también tiene un coste.
Gráfica de tiempo: el tiempo es proporcional al número de operaciones. Con 10⁹ operaciones por segundo, 10⁶ operaciones tardan 1 ms.
Cuando los datos crecen, el coste crece a un ritmo concreto. La notación O(·) guarda solo este ritmo y ignora las constantes.
O(log n) crece muy poco: cuando n pasa de 1 a 20, solo llega a ≈ 4,3, mientras que O(n) llega a 20.
Con n pequeño todas las curvas parecen cercanas; a partir de n ≈ 10 la cuadrática se separa de las demás.
| Función | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| O(log n) | ≈ 3 | ≈ 10 | ≈ 20 |
| O(n) | 10 | 1 000 | 1 000 000 |
| O(n log n) | ≈ 33 | ≈ 10 000 | ≈ 20 000 000 |
| O(n²) | 100 | 1 000 000 | 1 000 000 000 000 |
O(1): el coste no depende de n. O(log n): cada paso divide entre 2 (dicotómica). O(n): proporcional a n (búsqueda lineal). O(n log n): típico de los buenos algoritmos de ordenación. O(n²): dos bucles anidados (burbuja, selección).
Cuando n se multiplica por 10: con O(n) el coste se multiplica por 10; con O(n²), por 100; con O(log n), casi no cambia.
Ignora las constantes y los términos pequeños: 3n² + 5n es O(n²).
El orden respecto a n explica cómo crece el coste cuando crecen los datos. Es la idea más importante de este mapa.
Cuando n se multiplica por 10, un coste O(n) también se multiplica por 10, pero un coste O(n²) se multiplica por 100.
Si el coste es O(n), el trabajo crece igual que los datos. Si es O(n²), con el doble de datos el trabajo se cuadruplica.
Lo que importa es cómo crece, no el número exacto de operaciones.
El mismo algoritmo puede tardar más o menos según los datos. Por eso el análisis distingue tres casos: mejor, medio y peor.
| Caso | Burbuja | Dicotómica |
|---|---|---|
| Mejor | n−1 comparaciones (lista ya ordenada) | 1 paso (el medio es el buscado) |
| Medio | ≈ n²/2 comparaciones | ≈ log₂ n pasos |
| Peor | n(n−1)/2 comparaciones | ⌊log₂ n⌋ + 1 pasos |
Si el cociente es cercano a 2, el crecimiento es aproximadamente lineal; si es cercano a 4, cuadrático. El ruido del navegador hace que no sea exacto: por eso se hace la mediana de 3 repeticiones.
Para evaluar un algoritmo hay que mirar los datos de peor caso (las que más lo hacen trabajar), pero también el caso medio, que suele ser el más habitual.
Una sola medida de un caso concreto no dice cuál es el peor. Analiza el caso y después mide.
La búsqueda lineal mira los elementos uno a uno hasta encontrar lo que buscas. Es el método más simple y sirve de referencia para comparar con la búsqueda dicotómica.
Se compara cada elemento con el valor buscado hasta encontrarlo o llegar al final.
| Caso | Comparaciones | Con n = 1 000 000 |
|---|---|---|
| Mejor (es el primero) | 1 | 1 |
| Medio (está en la mitad) | n / 2 | 500 000 |
| Peor (es el último o no está) | n | 1 000 000 |
El coste es O(n): cada elemento se examina como máximo una vez.
Cuando des un coste, di qué caso es: el mejor, el medio o el peor.
Gráfica de tiempo: el tiempo es proporcional al número de operaciones. Con 10⁹ operaciones por segundo, 10⁶ operaciones tardan 1 ms.
La ordenación por selección busca el mínimo de la parte no ordenada y lo pone delante. Repítelo hasta que toda la lista esté ordenada.
La primera pasada busca el mínimo entre n elementos (n−1 comparaciones) y lo pone en la primera posición. La siguiente busca entre n−1 elementos, y así hasta el último.
| n (datos) | Comparaciones (siempre) |
|---|---|
| 10 | 45 |
| 100 | 4 950 |
| 1 000 | 499 500 |
Total: (n−1) + (n−2) + … + 1 = n(n−1)/2, es decir O(n²) en todos los casos. Hace como máximo n−1 intercambios.
La selección hace siempre las mismas comparaciones; la burbuja puede detenerse antes si la lista ya está ordenada.
Gráfica de tiempo: el tiempo es proporcional al número de operaciones. Con 10⁹ operaciones por segundo, 10⁶ operaciones tardan 1 ms.
La ordenación por inserción toma cada elemento y lo coloca en el lugar que le corresponde dentro de la parte ya ordenada.
En el peor caso (lista invertida) hace n(n−1)/2 comparaciones: O(n²). En el mejor caso (lista ya ordenada) solo hace n−1: O(n).
La inserción es rápida cuando la lista ya está casi ordenada.
La ordenación por fusión parte la lista por la mitad, ordena cada mitad y después las une.
Cada nivel de divisiones hace n pasos y hay log₂ n niveles. El coste es O(n log n) en todos los casos.
Para listas grandes es mucho más rápida que la burbuja.
Medir es fácil de hacer mal. Estos son los errores más habituales, y cómo evitarlos.
Antes de decir que un algoritmo es más rápido, pregúntate: con qué datos, en qué máquina y cuántas veces lo he medido.
Lee cada situación y elige qué concepto explica el caso. Si eliges uno que también está, pero no es el principal, te lo diremos.
Un programa suma 1 000 000 de números dentro de un bucle. ¿Qué concepto explica por qué el coste es alto?
Un programa suma 1 000 000 de números dentro de un bucle. ¿Qué concepto explica por qué el coste es alto?
Buscas el número 42 en una lista ordenada de un millón de números. Miras el medio, descartas la mitad y, en unos 20 pasos, lo encuentras. ¿Qué algoritmo es?
Un algoritmo recorre la lista comparando vecinos e intercambiándolos. Con la lista invertida hace n(n−1)/2 comparaciones. ¿Qué algoritmo es?
Un algoritmo tarda 4 veces más cuando duplicas los datos. ¿Qué concepto describe cómo crece su coste?
Buscas un número en una lista desordenada de n elementos y lo comparas con cada elemento hasta encontrarlo. ¿Qué algoritmo es?
Un algoritmo busca el mínimo de la parte no ordenada y lo pone delante. Hace n(n−1)/2 comparaciones aunque la lista ya esté ordenada. ¿Qué algoritmo es?
Este mapa reúne conceptos clásicos del análisis de algoritmos y los objetivos del currículo de las Illes Balears. Aquí tienes dónde comprobarlo y profundizar.