Comparing algorithms and ADTs in algorithms
Introducido| English | Significado |
|---|---|
| Big-O/bɪɡ əʊ/ | Notación Big-O |
| time complexity/taɪm kəmˈpleksɪti/ | Complejidad temporal |
| space complexity/speɪs kəmˈpleksɪti/ | Complejidad espacial |
| depth-first/depθ fɜːst/ | Exploración en profundidad |
| breadth-first/bredθ fɜːst/ | Exploración en anchura |
| binary tree/ˈbaɪnəri triː/ | Árbol binario |
El algoritmo que sobreviviría al universo
- Un vendedor debe visitar 25 ciudades y regresar a su punto de partida por la ruta más corta. Si se prueban todos los órdenes posibles, hay aproximadamente $10^{23}$ combinaciones. Una máquina que revisara un billón por segundo tardaría tres millones de años.
- Añadir una sola ciudad hace que el trabajo se multiplique por 25. No se trata de necesitar una computadora más rápida; es un enfoque que nunca funcionará, a cualquier velocidad y en cualquier hardware.
- Saber esto antes de escribir el programa es para lo que sirve el análisis de complejidad. Es la diferencia entre elegir un algoritmo y descubrir, meses después, que el tuyo no escala.
- Esta lección trata sobre Big-O (notación asintótica) para tiempo y espacio, y cómo las ADT moldean los algoritmos construidos sobre ellas.
Complejidad temporal
- La complejidad temporal describe cómo crece el tiempo de ejecución con el tamaño de la entrada $n$. Se escribe en notación Big-O, la cual conserva solo el término dominante y omite las constantes.
- $O(1)$ constante: el tiempo no depende de $n$ en absoluto. $O(\log n)$ logarítmica, como en la búsqueda binaria. $O(n)$ lineal, como en la búsqueda lineal. $O(n \log n)$, los buenos algoritmos de ordenamiento. $O(n^2)$ cuadrática, como en el ordenamiento burbuja e inserción.
- La razón por la que se omiten las constantes: son insignificantes. Un algoritmo $O(n^2)$ podría superar a uno $O(n \log n)$ para $n = 10$, pero en $n = 10{,}000$ nada pueden hacer las constantes para salvarlo.

Las curvas se cruzan una vez, y después eso el orden decide todo
How running time grows with n
Slide n upward and compare the curves: O(1) and O(log n) stay almost flat, O(n) rises steadily, O(n²) explodes. This is why Big-O — not a stopwatch — is how we compare algorithms on large inputs.
Which Big-O describes binary search?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Halving the range each step is logarithmic — O(log n).
Which Big-O describes bubble sort in the worst case?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Two nested loops over n elements give O(n²).
Match each algorithm to its time complexity.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Linear search is O(n), binary search O(log n), bubble sort O(n²).
Ejemplo resuelto: qué sucede al duplicar la entrada
- Un algoritmo tarda 4 segundos en procesar 1,000 elementos. Estime su tiempo en 2,000 elementos si es $O(n)$, y luego si es $O(n^2)$.
- $O(n)$: al duplicar $n$, se duplica el tiempo, así que aproximadamente 8 segundos.
- $O(n^2)$: al duplicar $n$, el tiempo se cuadruplica, por lo que aproximadamente 16 segundos. Con 10,000 elementos sería 100 veces el original, unos 400 segundos.
- $O(\log n)$ añadiría solo un paso extra, y $O(1)$ no cambiaría en absoluto. Razona desde el orden, no desde una fórmula.
An O(n squared) algorithm takes 4 seconds on 1,000 items. Roughly how many seconds will it take on 2,000?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Doubling n quadruples an O(n squared) time. The same doubling would take an O(n) algorithm from 4 seconds to 8.
Complejidad espacial
- La complejidad espacial es la memoria adicional que necesita un algoritmo, más allá de la propia entrada.
- El ordenamiento burbuja y el de inserción usan $O(1)$ de memoria adicional: trabajan in situ, necesitando solo un par de variables. El ordenamiento por fusión usa $O(n)$, ya que construye un segundo arreglo.
- La recursión usa memoria de pila proporcional a su profundidad, porque cada llamada incompleta mantiene su propio marco.
- A menudo existe un compromiso entre tiempo y memoria: almacenar resultados para evitar recalcularlos, como hace la memorización, compra velocidad a costa de espacio.
Qué más influye en la elección
- Big-O trata sobre el crecimiento, no sobre la velocidad absoluta. Para una $n$ pequeña, un simple algoritmo $O(n^2)$ puede superar a uno complejo $O(n \log n)$, y es más fácil escribirlo correctamente.
- La estabilidad importa cuando una lista ya está ordenada según otro campo. La simplicidad importa porque un algoritmo sencillo tiene menos lugares donde ocultar un error.
- La respuesta honesta a "¿qué algoritmo?" suele nombrar tanto el orden como las condiciones: este, porque $n$ es grande y los datos llegan desordenados.
An "in place" sort:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
In-place algorithms (like bubble and insertion sort) sort within the original array, using constant extra space.
Why is bubble sort's space complexity O(1) even though it sorts an array of n items?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
It sorts in place. Merge sort is O(n) because it builds a second array, and recursion costs memory proportional to its depth.
ADT dentro de los algoritmos
- Los tipos de datos abstractos del tema 10 son la maquinaria de la que están construidos los algoritmos, y elegir uno moldea al algoritmo.
- Una pila proporciona una búsqueda profunda (depth-first): apila los vecinos, toma el más reciente, y la búsqueda se hunde por un camino antes de retroceder. La recursión usa la pila de llamadas exactamente para esto.
- Una cola proporciona una búsqueda amplitud (breadth-first): encola los vecinos, toma el más antiguo, y la búsqueda se expande hacia afuera en anillos, lo cual es lo que encuentra el camino más corto en un grafo no ponderado.
- Un árbol binario mantiene los valores ordenados para que la búsqueda descarte la mitad de los nodos restantes en cada paso, ofreciendo la $O(\log n)$ de la búsqueda binaria sobre una estructura que también puede crecer.
Which statements about Big-O are correct? Select todos that apply.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Big-O says nothing about seconds; it is about growth. That is why the crossover with a simpler algorithm exists at small sizes.
Ejemplo resuelto: el mismo grafo, dos búsquedas
- Se explora un laberinto desde una entrada. Contraste usar una pila con usar una cola.
- Con una pila, el último camino encontrado se explora a continuación, por lo que la búsqueda se hunde profundamente por una ruta hasta llegar a un callejón sin salida, y luego retrocede. Usa memoria proporcional a la profundidad del camino.
- Con una cola, el camino encontrado más antiguo se explora a continuación, por lo que la búsqueda examina todo lo que está a un paso de distancia, luego todo lo que está a dos pasos. Encuentra primero la ruta más corta, pero mantiene en memoria todas las posiciones a la distancia actual.
- Nombra la ADT, nombra el orden resultante de exploración y nombra la consecuencia.
A stack (LIFO) naturally drives a depth-first traversal, while a queue (FIFO) drives a breadth-first traversal.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
The ADT you choose decides the search order — stack goes deep first, queue explores level by level.
Match each ADT to the search it produces and its consequence.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Most recent first, or oldest first. That single choice decides whether the search goes deep or wide.
Errores comunes
- Big-O describe el crecimiento con el tamaño de la entrada, no segundos. Decir "es rápido" no es una respuesta de complejidad.
- Duplicar la entrada duplica el tiempo de un $O(n)$ y cuadruplica el de un $O(n^2)$. Razona desde el orden.
- La complejidad espacial es la memoria adicional, por eso un ordenamiento in situ es $O(1)$ aunque el arreglo tenga tamaño $n$.
- La pila da búsqueda profunda, la cola da búsqueda amplitud. Invertir ese par es el error central de varias preguntas.
Lo has entendido
- La complejidad temporal en Big-O describe el crecimiento con $n$: $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$; las constantes se omiten porque a gran escala el orden decide.
- Duplicar $n$ duplica $O(n)$ y cuadruplica $O(n^2)$; el cruce con un algoritmo "peor" solo existe para valores pequeños de $n$.
- La complejidad espacial es la memoria adicional: los ordenamientos in situ son $O(1)$, el ordenamiento por fusión es $O(n)$, y la recursión cuesta profundidad de pila.
- Una pila proporciona búsqueda profunda, una cola proporciona búsqueda amplitud, y un árbol binario reduce a la mitad los nodos restantes en cada paso.