Bienvenido al primer módulo de Algoritmos Avanzados. Antes de optimizar nada, necesitamos un lenguaje común para hablar de algoritmos: qué son exactamente, qué significa que uno sea "mejor" que otro y cómo expresar su coste de forma precisa e independiente de la máquina en la que se ejecuta. En esta lección construimos ese lenguaje: propiedades de un algoritmo, el modelo de cómputo RAM, la notación asintótica (O, Ω, Θ) y el pseudocódigo como herramienta de comunicación.

Para dar contexto a todo el curso trabajaremos con Rutalia, una empresa ficticia de logística urbana de última milla. Rutalia gestiona pedidos, ordena repartos y busca direcciones miles de veces al día. Cuando gestionaba 100 pedidos diarios, cualquier programa razonable funcionaba. Ahora procesa cerca de un millón, y de repente hay operaciones que tardan horas. Entender por qué ocurre eso —y anticiparlo antes de escribir código— es el objetivo de esta lección.

1. Qué es un algoritmo y qué propiedades debe cumplir
2. Corrección frente a eficiencia
3. El modelo de cómputo RAM
4. Notación asintótica: O, Ω y Θ
5. Jerarquía de órdenes de crecimiento
6. Pseudocódigo y su equivalencia con Python

Un algoritmo es un procedimiento computacional bien definido que toma uno o varios valores como entrada y produce uno o varios valores como salida, mediante una secuencia finita de pasos precisos.

Para que un procedimiento merezca llamarse algoritmo debe cumplir estas propiedades:

• Finitud: termina tras un número finito de pasos. Un proceso que puede no acabar nunca no es un algoritmo válido.
• Definición precisa (no ambigüedad): cada paso está especificado sin ambigüedad. "Elige un pedido razonable" no es un paso válido; "elige el pedido con menor hora límite de entrega" sí lo es.
• Entrada: cero o más valores dados antes de empezar (por ejemplo, la lista de pedidos del día).
• Salida: uno o más valores relacionados con la entrada (por ejemplo, la lista de pedidos ordenada por hora límite).
• Efectividad: cada operación es lo bastante básica como para poder ejecutarse mecánicamente en tiempo finito.

En Rutalia, "ordenar los repartos de la furgoneta 7 por hora límite de entrega" es un problema; el procedimiento concreto que lo resuelve (por ejemplo, un algoritmo de ordenación) es el algoritmo; y el código Python que lo implementa es el programa. Distinguir los tres niveles es importante: un mismo problema admite muchos algoritmos, y un mismo algoritmo admite muchas implementaciones.

Un algoritmo se evalúa en dos dimensiones independientes:

Dos ideas clave:

• La corrección es innegociable. Un algoritmo rapidísimo que a veces pierde pedidos no sirve de nada. La corrección se argumenta razonando sobre el algoritmo (casos base, invariantes de bucle), no solo probando con ejemplos: las pruebas pueden mostrar la presencia de errores, pero no su ausencia.
• La eficiencia se mide en función del tamaño de la entrada, que llamaremos habitualmente n. No nos interesa "cuántos milisegundos tarda en mi portátil", sino cómo crece el coste cuando n crece. Ese crecimiento es lo que decide si el sistema de Rutalia sobrevive al salto de 100 pedidos a 1 000 000.

Un ejemplo ilustrativo. Supongamos dos algoritmos correctos para buscar una dirección entre n direcciones registradas:

• El algoritmo A hace del orden de n operaciones.
• El algoritmo B hace del orden de log₂ n operaciones (requiere datos ordenados).

Con n = 100, A hace ~100 operaciones y B ~7: la diferencia es irrelevante. Con n = 1 000 000, A hace un millón de operaciones y B ~20. Si esa búsqueda se ejecuta una vez por cada pedido que entra, la diferencia deja de ser académica: es la diferencia entre un servidor tranquilo y uno saturado. En la lección 01-02 aprenderemos a calcular estos costes; aquí nos basta con saber expresarlos.

Para contar operaciones necesitamos acordar qué cuenta como "una operación". El modelo estándar es la máquina RAM (Random Access Machine), una idealización de un ordenador real con estas reglas:

• Hay una memoria de celdas, y acceder a cualquier celda cuesta lo mismo (tiempo constante), da igual su posición. De ahí "acceso aleatorio".
• Las operaciones elementales cuestan una unidad de tiempo cada una: aritmética básica (+, -, *, /, módulo), comparaciones (<, ==), asignaciones, lecturas/escrituras de una celda, y saltos de control (if, llamada, retorno).
• Las instrucciones se ejecutan una detrás de otra, sin paralelismo.
• Cada celda almacena un número de tamaño razonable (no hacemos trampas metiendo un fichero entero en "una celda").

Es una simplificación deliberada: ignora cachés, pipelines y detalles del hardware real. A cambio, nos da algo valiosísimo: los análisis hechos sobre el modelo RAM predicen el comportamiento relativo de los algoritmos en cualquier máquina real. Si en el modelo RAM el algoritmo B crece mucho más despacio que el A, en producción también lo hará (a partir de cierto tamaño de entrada).

Precaución práctica con Python: algunas operaciones que se escriben en una línea no son elementales. Por ejemplo:

Cada una de estas líneas esconde un coste proporcional a n. Al analizar código Python hay que "traducir" mentalmente cada construcción al número de operaciones RAM que implica.

Contar operaciones exactas es tedioso y poco útil: ¿de verdad importa si son 3n + 7 o 5n + 2 operaciones? Lo que importa es que ambas crecen linealmente. La notación asintótica captura exactamente eso: el comportamiento del coste cuando n se hace grande, ignorando constantes multiplicativas y términos de orden inferior.

Definición formal: f(n) = O(g(n)) si existen constantes positivas c y n₀ tales que f(n) ≤ c · g(n) para todo n ≥ n₀.

Intuición: a partir de cierto tamaño, f nunca crece más deprisa que g (salvo constante). Es una promesa del tipo "como mucho, así de mal". Ejemplo: 3n + 7 = O(n) (basta tomar c = 4 y n₀ = 7, porque 3n + 7 ≤ 4n cuando n ≥ 7). También es cierto que 3n + 7 = O(n²) —la cota superior no tiene por qué ser ajustada—, aunque por convención damos la más ajustada que sepamos demostrar.

Definición formal: f(n) = Ω(g(n)) si existen constantes positivas c y n₀ tales que f(n) ≥ c · g(n) para todo n ≥ n₀.

Intuición: a partir de cierto tamaño, f crece al menos tan deprisa como g. Es la promesa contraria: "como poco, esto cuesta". Ejemplo: cualquier algoritmo que necesite mirar todos los pedidos al menos una vez es Ω(n): no hay implementación posible que lo baje de ahí.

Definición formal: f(n) = Θ(g(n)) si f(n) = O(g(n)) y a la vez f(n) = Ω(g(n)).

Intuición: f y g crecen al mismo ritmo, salvo constantes. Es la caracterización exacta del orden de crecimiento. Ejemplo: 3n + 7 = Θ(n).

Reglas prácticas para simplificar:

• Se descartan las constantes multiplicativas: 500n = O(n).
• Domina el término mayor: n² + 1000n + 3 = Θ(n²), porque para n grande el término n² eclipsa a los demás.
• Las bases de los logaritmos no importan: log₂ n y log₁₀ n difieren en una constante, así que ambas son Θ(log n).

Un matiz habitual: en la práctica profesional casi todo el mundo dice "este algoritmo es O(n log n)" queriendo decir Θ(n log n). Es un abuso de lenguaje tolerado; en este curso usaremos Θ cuando afirmemos el orden exacto y O cuando solo acotemos por arriba.

Nota importante: O, Ω y Θ hablan de funciones de coste, no de "peor caso / mejor caso". Se puede dar una cota O del mejor caso o una Ω del peor caso. La relación entre casos (mejor, peor, medio) y estas notaciones la veremos con calma en la lección 01-02.

Los órdenes de crecimiento habituales, de crecimiento más lento a más rápido:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

Para hacerlos tangibles, supongamos una máquina que ejecuta 10⁸ operaciones elementales por segundo (un ordenador modesto) y veamos cuánto tardaría cada orden de crecimiento con los volúmenes de Rutalia:

Tres lecturas de esta tabla que conviene interiorizar:

• Con n pequeño todo funciona. Con 100 pedidos, hasta el algoritmo cuadrático responde en una décima de milisegundo. Por eso los problemas de rendimiento aparecen después, cuando el negocio crece. El código de Rutalia no "se rompió": simplemente n cambió de escala.
• El salto de O(n log n) a O(n²) es el precipicio práctico más común. Ordenar un millón de repartos: 0,2 segundos. Comparar cada pedido con cada otro para detectar duplicados de forma ingenua: casi 3 horas. Mismo hardware, mismo lenguaje.
• Los órdenes exponenciales y factoriales no se arreglan con hardware. Si un algoritmo O(2ⁿ) es inviable para n = 100, comprar una máquina 1000 veces más rápida solo permite llegar a n ≈ 110. Contra el crecimiento exponencial, la única arma es un algoritmo mejor (o aceptar soluciones aproximadas, como veremos en el módulo 2).

El pseudocódigo es una descripción de un algoritmo a medio camino entre el lenguaje natural y un lenguaje de programación: lo bastante preciso para no ser ambiguo, lo bastante abstracto para no distraerse con la sintaxis. Es el idioma en el que se escriben los libros de algoritmia y en el que conviene pensar antes de programar.

Convenciones habituales y su traducción directa a Python:

Ejemplo completo. Pseudocódigo para encontrar el pedido con la hora límite más temprana (el más urgente) de una furgoneta:

Y su traducción literal a Python:

Observa cómo cada línea del pseudocódigo corresponde a una construcción de Python, y cómo los comentarios ya apuntan al conteo de operaciones (cuántas veces se ejecuta cada línea). El bucle visita cada pedido exactamente una vez, así que el coste es proporcional a n: este algoritmo es Θ(n). El análisis sistemático de este tipo de código —incluidos bucles anidados y casos mejor/peor/medio— es el tema de la próxima lección.

Consejos para escribir buen pseudocódigo:

• Nombra las variables por su significado (hora_limite, no x).
• Explicita las precondiciones (¿puede la lista estar vacía?).
• No incluyas detalles irrelevantes del lenguaje (gestión de excepciones, tipos exactos), pero sí todo lo que afecte a la corrección o al coste.
• Si un paso esconde trabajo no constante ("buscar d en la lista"), sé consciente de ello: al analizar, ese paso no cuesta 1.

• Confundir O con "peor caso". O es una cota superior sobre una función; puede aplicarse al peor caso, al mejor o al medio. Decir "el mejor caso de este algoritmo es O(n)" es perfectamente legítimo.
• Creer que O(1) significa "rápido". Significa "coste que no depende de n". Una operación O(1) puede costar 10 segundos fijos; una O(n) con constante minúscula puede ganarle para todos los n realistas. La notación asintótica compara crecimientos, no tiempos absolutos.
• Ignorar las constantes cuando n es pequeño. Para listas de 20 pedidos, un algoritmo O(n²) sencillo puede ser más rápido en la práctica que uno O(n log n) sofisticado. La asintótica manda cuando n crece; el sentido común manda siempre.
• Olvidar el coste oculto de las operaciones de Python. x in lista, lista.insert(0, x), lista[:] o un slice cuestan O(n), aunque quepan en una línea. Es el error número uno al analizar código Python.
• Escribir pseudocódigo ambiguo. Si dos personas pueden interpretar un paso de forma distinta, no es pseudocódigo: es prosa. Reescríbelo hasta que solo admita una lectura.
• Consejo: cuando dudes del orden de crecimiento, pregúntate qué pasa si n se multiplica por 10. ¿El coste se multiplica por 10 (lineal), por 100 (cuadrático) o casi no cambia (logarítmico)? Esta prueba mental resuelve la mayoría de dudas.

Simplifica cada función de coste a su notación Θ y ordénalas de menor a mayor crecimiento:

1. f₁(n) = 4n² + 100n + 7
2. f₂(n) = 50·n·log n + 3n
3. f₃(n) = 2ⁿ + n¹⁰
4. f₄(n) = 1000 (constante)
5. f₅(n) = 7n + 12·log n

El sistema de detección de pedidos duplicados de Rutalia ejecuta exactamente n²/2 operaciones elementales para n pedidos, en una máquina de 10⁸ operaciones por segundo.

1. ¿Cuánto tarda con n = 1 000, n = 100 000 y n = 1 000 000?
2. Un ingeniero propone un algoritmo alternativo de 20 · n · log₂ n operaciones. ¿Cuánto tardaría con n = 1 000 000? ¿A partir de qué escala aproximada compensa el cambio?

Traduce a Python el siguiente pseudocódigo, que comprueba si algún pedido de la furgoneta supera el peso máximo permitido, e indica razonadamente su orden de crecimiento en el peor caso y en el mejor caso.

Solución 1

1. f₁ = Θ(n²) — domina 4n²; se descartan la constante y los términos menores.
2. f₂ = Θ(n log n) — n log n domina a n.
3. f₃ = Θ(2ⁿ) — cualquier exponencial domina a cualquier polinomio, incluso a n¹⁰.
4. f₄ = Θ(1) — no depende de n.
5. f₅ = Θ(n) — n domina a log n.

Orden de menor a mayor crecimiento: f₄ (Θ(1)) < f₅ (Θ(n)) < f₂ (Θ(n log n)) < f₁ (Θ(n²)) < f₃ (Θ(2ⁿ)).

Solución 2

1. Con n = 1 000: 10⁶/2 = 5·10⁵ operaciones → 0,005 s. Con n = 100 000: 10¹⁰/2 = 5·10⁹ → 50 s. Con n = 1 000 000: 10¹²/2 = 5·10¹¹ → 5 000 s ≈ 83 minutos. Observa el patrón cuadrático: multiplicar n por 10 multiplica el tiempo por 100.
2. Con n = 1 000 000: log₂(10⁶) ≈ 20, luego 20 · 10⁶ · 20 = 4·10⁸ operaciones → 4 segundos. Igualando n²/2 = 20·n·log₂ n se obtiene n = 40·log₂ n, que se cumple alrededor de n ≈ 350. Es decir: para menos de unos ~350 pedidos el algoritmo cuadrático (con su constante pequeña) es competitivo; a la escala actual de Rutalia, el cambio es imprescindible. Moraleja: las constantes deciden con n pequeño; el orden de crecimiento decide con n grande.

Solución 3

• Peor caso: ningún pedido supera el máximo (o solo lo supera el último). El bucle recorre los n pedidos → Θ(n).
• Mejor caso: el primer pedido ya supera el máximo. Se hace una sola comparación → Θ(1).

Nota cómo un mismo algoritmo tiene funciones de coste distintas según el caso; formalizar esta distinción es parte de la próxima lección. Errores comunes aquí: olvidar el return False final (la función devolvería None), o acumular los resultados en una lista en vez de salir en cuanto se encuentra el primero (se perdería el mejor caso Θ(1)).

En esta lección hemos construido el vocabulario fundamental del curso. Un algoritmo es un procedimiento finito, preciso y efectivo que transforma entradas en salidas; se juzga primero por su corrección y después por su eficiencia. Para medir la eficiencia de forma independiente de la máquina usamos el modelo RAM (cada operación elemental cuesta 1) y la notación asintótica: O acota por arriba, Ω por abajo y Θ caracteriza el crecimiento exacto. La jerarquía de órdenes —de O(1) a O(n!)— explica por qué el software de Rutalia funcionaba con 100 pedidos y se ahoga con un millón: no es cuestión de hardware, sino de crecimiento. Finalmente, el pseudocódigo nos da un idioma preciso para diseñar antes de programar, con traducción directa a Python.

Ya sabemos expresar costes; el siguiente paso es calcularlos. En la próxima lección, Análisis de Complejidad, aprenderemos las técnicas sistemáticas para determinar la complejidad temporal y espacial de un algoritmo: conteo de operaciones, bucles anidados y dependientes, análisis por casos (mejor, peor, medio), análisis amortizado y una primera aproximación a las recurrencias. Analizaremos funciones reales del código de Rutalia y descubriremos, con números, dónde se esconde ese proceso que tarda horas.