Comparing algorithms and ADTs in algorithms · Comparando algoritmos y ADTs en algoritmos
| English | Español |
|---|---|
| Big-O/bɪɡ əʊ/ | 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/ | profundidad primero |
| breadth-first/bredθ fɜːst/ | amplitud primero |
| binary tree/ˈbaɪnəri triː/ | árbol binario |
The algorithm that would outlive the universe
- A salesman must visit 25 cities and return home by the shortest route. Try every order and there are about $10^{23}$ of them. A machine checking a billion a second would take three million years.
- Add one more city and the work multiplies by 25. That is not a computer that needs to be faster; it is an approach that can never work, at any speed, on any hardware.
- Knowing that before you write the program is what complexity analysis is for. It is the difference between choosing an algorithm and discovering, months later, that yours does not scale.
- This lesson is Big-O 大O表示法 for time and space, and how ADTs shape the algorithms built on them.
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.
Time complexity
- Time complexity 时间复杂度 describes how the running time grows with the input size $n$. It is written in Big-O notation, which keeps only the dominant term and drops constants.
- $O(1)$ constant, the time does not depend on $n$ at all. $O(\log n)$ logarithmic, as in binary search. $O(n)$ linear, as in linear search. $O(n \log n)$, the good sorts. $O(n^2)$ quadratic, as in bubble and insertion sort.
- The reason constants are dropped: they are swamped. An $O(n^2)$ algorithm might beat an $O(n \log n)$ one for $n = 10$, but at $n = 10{,}000$ nothing about the constants can save it.
The curves cross once, and after that the order decides everything
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 · Cómo crece el tiempo de ejecución con 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. · Desliza n hacia arriba y compara las curvas: O(1) y O(log n) permanecen casi planas, O(n) sube constantemente, O(n²) explota. Por eso Big-O —no un cronómetro— es cómo comparamos algoritmos en entradas grandes.
Which Big-O describes binary search? · ¿Qué Big-O describe la búsqueda binaria?
Halving the range each step is logarithmic — O(log n). · Reducir a la mitad el rango en cada paso es logarítmico — O(log n).
Which Big-O describes bubble sort in the worst case? · ¿Qué Big-O describe bubble sort en el peor caso?
Two nested loops over n elements give O(n²). · Dos bucles anidados sobre n elementos dan O(n²).
Match each algorithm to its time complexity. · Asocia cada algoritmo con su complejidad temporal.
Linear search is O(n), binary search O(log n), bubble sort O(n²). · La búsqueda lineal es O(n), la búsqueda binaria O(log n), bubble sort O(n²).
Worked example: what doubling the input does
- An algorithm takes 4 seconds on 1,000 items. Estimate its time on 2,000 items if it is $O(n)$, then if it is $O(n^2)$.
- $O(n)$: doubling $n$ doubles the time, so about 8 seconds.
- $O(n^2)$: doubling $n$ quadruples the time, so about 16 seconds. At 10,000 items it would be 100 times the original, about 400 seconds.
- $O(\log n)$ would add only a single step, and $O(1)$ would not change at all. Reason from the order, not from a formula.
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? · Un algoritmo O(n²) tarda 4 segundos en 1,000 elementos. ¿Aproximadamente cuántos segundos tardará en 2,000?
Doubling n quadruples an O(n squared) time. The same doubling would take an O(n) algorithm from 4 seconds to 8. · Duplicar n cuadruplica el tiempo en un algoritmo O(n²). La misma duplicación tomaría a un algoritmo O(n) pasar de 4 a 8 segundos.
Space complexity
- Space complexity 空间复杂度 is the extra memory an algorithm needs, beyond the input itself.
- Bubble and insertion sort use $O(1)$ extra memory: they work in place, needing only a couple of variables. Merge sort uses $O(n)$, since it builds a second array.
- Recursion uses stack memory proportional to its depth, because every unfinished call keeps its own frame.
- There is often a time and memory trade-off: storing results to avoid recomputing them, as memoisation does, buys speed with space.
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.
What else decides the choice
- Big-O is about growth, not absolute speed. For a small $n$, a simple $O(n^2)$ algorithm can beat a complicated $O(n \log n)$ one, and it is easier to write correctly.
- Stability matters when a list is already ordered by another field. Simplicity matters because a simple algorithm has fewer places to hide a bug.
- The honest answer to "which algorithm" often names the order and the conditions: this one, because $n$ is large and the data arrives unsorted.
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: · Una ordenación "in place":
In-place algorithms (like bubble and insertion sort) sort within the original array, using constant extra space. · Los algoritmos in-place (como bubble y insertion sort) ordenan dentro de la matriz original, usando espacio constante extra.
Why is bubble sort's space complexity O(1) even though it sorts an array of n items? · ¿Por qué la complejidad espacial de bubble sort es O(1) aunque ordene una matriz de n elementos?
It sorts in place. Merge sort is O(n) because it builds a second array, and recursion costs memory proportional to its depth. · Ordena in-place. Merge sort es O(n) porque construye una segunda matriz, y la recursión consume memoria proporcional a su profundidad.
ADTs inside algorithms
- The abstract data types from topic 10 are the machinery algorithms are built from, and choosing one shapes the algorithm.
- A stack gives depth-first 深度优先 search: push the neighbours, take the most recent, and the search plunges down one path before backing up. Recursion uses the call stack for exactly this.
- A queue gives breadth-first 广度优先 search: enqueue the neighbours, take the oldest, and the search spreads outward in rings, which is what finds the shortest path in an unweighted graph.
- A binary tree 二叉树 keeps values in order so that a search discards half the remaining nodes at each step, giving binary search's $O(\log n)$ over a structure that can also grow.
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 all · todos that apply. · ¿Cuáles son las afirmaciones correctas sobre Big-O? Selecciona todas las que apliquen.
Big-O says nothing about seconds; it is about growth. That is why the crossover with a simpler algorithm exists at small sizes. · Big-O no dice nada sobre segundos; trata sobre crecimiento. Por eso existe el punto de cruce con un algoritmo más simple en tamaños pequeños.
Worked example: the same graph, two searches
- A maze is explored from one entrance. Contrast using a stack with using a queue.
- With a stack, the most recently found path is explored next, so the search goes deep down one route until it dead-ends, then backtracks. It uses memory proportional to the depth of the path.
- With a queue, the oldest found path is explored next, so the search examines everything one step away, then everything two steps away. It finds the shortest route first, but holds every position at the current distance in memory.
- Name the ADT, name the resulting order of exploration, and name the consequence.
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. · Una pila (LIFO) impulsa naturalmente un recorrido en profundidad, mientras que una cola (FIFO) impulsa un recorrido en anchura.
The ADT you choose decides the search order — stack goes deep first, queue explores level by level. · El ADT que elijas decide el orden de búsqueda: la pila va profundo primero, la cola explora nivel por nivel.
Match each ADT to the search it produces and its consequence. · Asocia cada ADT con la búsqueda que produce y su consecuencia.
Most recent first, or oldest first. That single choice decides whether the search goes deep or wide. · Reciente primero, o antiguo primero. Esa única elección decide si la búsqueda va profunda o amplia.
Marks that slip away
- Big-O describes growth with input size, not seconds. "It is fast" is not a complexity answer.
- Doubling the input doubles an $O(n)$ time and quadruples an $O(n^2)$ one. Reason from the order.
- Space complexity is the extra memory, which is why an in-place sort is $O(1)$ even though the array is size $n$.
- Stack gives depth-first, queue gives breadth-first. Getting that pair the right way round is the whole of several questions.
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.
You've got it
- time complexity in Big-O describes growth with $n$: $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$; constants are dropped because at scale the order decides
- doubling $n$ doubles $O(n)$ and quadruples $O(n^2)$; the crossover with a "worse" algorithm only exists for small $n$
- space complexity is the extra memory: in place sorts are $O(1)$, merge sort is $O(n)$, and recursion costs stack depth
- a stack gives depth-first search, a queue gives breadth-first, and a binary tree halves the remaining nodes at each step
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.