Data Structure & Algorithms
Fundamentos para analizar tiempo y espacio con Big O, Omega y Theta, definir el tamaño de entrada y comparar órdenes de crecimiento con precisión.
La complejidad describe cómo crece el costo de una solución cuando crece su entrada. No intenta predecir milisegundos exactos; permite comparar algoritmos sin depender de un computador, lenguaje o conjunto pequeño de pruebas.
Dos recursos se analizan principalmente:
Antes de escribir O(n), define qué representa n y qué caso estás analizando.
El tamaño no siempre es array.length.
Puede ser:
n: cantidad de elementos de un array;V y E: vértices y aristas de un grafo;rows × cols: celdas de una matriz;L: longitud de una clave;n y m: tamaños de dos colecciones;Ejemplo:
function containsCommonValue(
left: readonly number[],
right: readonly number[],
): boolean {
for (const a of left) {
for (const b of right) {
if (a === b) return true;
}
}
return false;
}Si left tiene n elementos y right tiene m, el peor caso es O(nm), no necesariamente O(n²).
El análisis suele usar un modelo RAM simplificado: operaciones como leer un índice, comparar valores pequeños o asignar una referencia cuestan una unidad constante.
Es una abstracción. En la práctica, comparar strings largos, copiar objetos o hacer operaciones con enteros arbitrariamente grandes no siempre cuesta O(1).
Ejemplo:
if (users[index].name === targetName) {
// The string comparison may depend on the compared length.
}La operación dominante puede incluir la longitud de las claves.
O(g(n)) es una cota superior asintótica. Indica que, a partir de cierto tamaño, el crecimiento no supera una constante multiplicada por g(n).
Formalmente:
f(n) ∈ O(g(n))
si existen c > 0 y n₀ tales que
0 ≤ f(n) ≤ c · g(n) para todo n ≥ n₀Si un algoritmo tarda exactamente 3n + 7 operaciones:
3n + 7 ∈ O(n)También pertenece a O(n²), pero O(n) es una cota más informativa.
Big O no significa automáticamente “peor caso”. Puedes describir con Big O el mejor, promedio o peor caso, siempre que indiques cuál.
Ω(g(n)) es una cota inferior asintótica.
f(n) ∈ Ω(g(n))
si existen c > 0 y n₀ tales que
0 ≤ c · g(n) ≤ f(n) para todo n ≥ n₀Si una función siempre debe leer n valores para calcular su suma, su tiempo es Ω(n).
Una cota inferior puede describir:
El límite Ω(n log n) de comparison sorting se aplica al peor caso de algoritmos que solo obtienen información comparando claves arbitrarias.
Θ(g(n)) es una cota ajustada: la función está acotada por arriba y por abajo por el mismo crecimiento.
f(n) ∈ Θ(g(n))
si f(n) ∈ O(g(n)) y f(n) ∈ Ω(g(n))Para un loop que siempre recorre todos los elementos:
function sum(values: readonly number[]): number {
let total = 0;
for (const value of values) {
total += value;
}
return total;
}El tiempo es Θ(n): hace una cantidad proporcional a n tanto como cota superior como inferior.
En comunicación cotidiana se usa mucho O(n) aunque Θ(n) sea más preciso. Lo importante es no convertir Big O en una afirmación falsa sobre una garantía exacta.
| Complejidad | Idea | Ejemplo |
|---|---|---|
| O(1) | No crece con n | Acceso por índice |
| O(log n) | Reduce el espacio por un factor | Binary search |
| O(n) | Recorre la entrada | Linear search |
| O(n log n) | Trabajo lineal por niveles logarítmicos | Merge sort |
| O(n²) | Compara muchas parejas | Selection sort |
| O(n³) | Combinaciones de tres dimensiones | Floyd-Warshall |
| O(2ⁿ) | Dos decisiones por elemento | Enumerar subsets |
| O(n!) | Todos los órdenes posibles | Enumerar permutations |
El orden importa más cuando n crece. Para entradas pequeñas, constantes y overhead pueden dominar.
T(n) = 4n + 20Para entradas grandes, duplicar n aproximadamente duplica el término dominante. La constante 4 y el 20 no cambian la familia de crecimiento:
T(n) = Θ(n)Esto no significa que las constantes no importen en producción. Dos algoritmos O(n) pueden diferir mucho en caché, asignaciones o costo de cada operación. Big O responde una pregunta diferente.
T(n) = 3n² + 20n + 500Cuando n crece, n² domina:
T(n) = Θ(n²)No elimines términos que dependen de variables independientes:
O(n + m)No puede simplificarse a O(n) si m puede crecer por separado.
for (const value of values) {
process(value);
}
for (const value of values) {
validate(value);
}Los costos se suman:
O(n) + O(n) = O(2n) = O(n)Si una fase cuesta O(n) y otra O(n²), domina la segunda:
O(n + n²) = O(n²)for (let i = 0; i < values.length; i += 1) {
for (let j = 0; j < values.length; j += 1) {
inspect(values[i], values[j]);
}
}Ejecuta n × n: Θ(n²).
Pero no todo loop anidado es cuadrático:
let right = 0;
for (let left = 0; left < values.length; left += 1) {
while (right < values.length && condition(left, right)) {
right += 1;
}
}Si right nunca retrocede, avanza como máximo n veces durante toda la función. El tiempo puede ser O(n), más el trabajo del loop externo. Debes contar movimientos totales, no multiplicar loops visualmente.
for (let i = 0; i < n; i += 1) {
for (let j = i + 1; j < n; j += 1) {
compare(i, j);
}
}Cantidad de iteraciones:
(n - 1) + (n - 2) + ... + 1
= n(n - 1) / 2
= Θ(n²)Reducir a la mitad las parejas cambia una constante, no el orden.
Un proceso es logarítmico cuando reduce el problema por un factor constante:
n → n/2 → n/4 → n/8 → ... → 1La cantidad de divisiones es aproximadamente log₂ n.
La base del logaritmo se ignora en Big O porque:
log_a n = log_b n / log_b aLa diferencia es una constante.
function linearSearch(values: readonly number[], target: number): number {
for (let index = 0; index < values.length; index += 1) {
if (values[index] === target) return index;
}
return -1;
}Θ(1), está al inicio.Θ(n), está al final o no existe.No digas “average O(n/2)”. n/2 sigue siendo Θ(n), y además el promedio necesita supuestos.
El análisis esperado usa aleatoriedad del algoritmo o una distribución probabilística.
Ejemplo: quick sort con pivot aleatorio tiene tiempo esperado O(n log n), aunque conserva peor caso O(n²).
No confundas:
Cuenta memoria adicional que crece con la entrada:
function copy(values: readonly number[]): number[] {
return [...values];
}Tiempo Θ(n), espacio adicional Θ(n).
function reverseInPlace(values: number[]): void {
let left = 0;
let right = values.length - 1;
while (left < right) {
[values[left], values[right]] = [values[right], values[left]];
left += 1;
right -= 1;
}
}Tiempo Θ(n), espacio auxiliar Θ(1).
function countdown(n: number): void {
if (n === 0) return;
countdown(n - 1);
}Tiempo Θ(n) y espacio Θ(n) por profundidad recursiva, aunque no exista una colección explícita.
Para un árbol balanceado, una DFS recursiva puede usar O(log n) de stack; para uno degenerado, O(n).
Generar todos los subsets necesita almacenar hasta 2^n resultados. Una función puede usar solo O(n) de stack auxiliar, pero la salida materializada es exponencial.
Aclara si reportas:
Algunas complejidades dependen de cuánto resultado se produce.
Una consulta de rango en un BST balanceado puede costar:
O(log n + k)k es la cantidad de elementos devueltos. Ningún algoritmo puede materializar k resultados en menos de Ω(k) tiempo.
Knapsack con capacidad W puede resolverse en O(nW). Parece polinomial, pero W es un valor numérico cuya representación usa log W bits.
Por eso se llama pseudo-polinomial: es polinomial respecto al valor de W, no respecto al tamaño de su representación.
Esta función no es necesariamente lineal:
function prefixes(text: string): string[] {
const result: string[] = [];
for (let index = 1; index <= text.length; index += 1) {
result.push(text.slice(0, index));
}
return result;
}Si cada slice copia index caracteres, el trabajo total es:
1 + 2 + ... + n = Θ(n²)No cuentes solo iteraciones; cuenta el costo de lo que ocurre dentro.
Con adjacency list, BFS y DFS cuestan O(V + E) porque visitan cada vértice y examinan cada entrada de arista.
Con adjacency matrix, explorar vecinos de cada vértice cuesta O(V), para un total O(V²).
La complejidad depende del algoritmo y de la representación.
Lookup suele describirse como O(1) promedio o esperado. El peor caso puede ser O(n) por colisiones adversariales.
Una inserción puede disparar rehashing O(n), pero ser O(1) amortizado a lo largo de muchas inserciones.
Cada calificativo importa.
Una buena frase es:
Con adjacency list y una queue con operaciones constantes, BFS tarda
O(V + E)y usaO(V)de memoria adicional.
Una frase incompleta es:
BFS es
O(n).
La primera define variables, representación y estructura auxiliar.
n = 0;O(n/2) es una categoría distinta de O(n).slice, shift, sorting o comparación de strings.O(n + m) a O(n) sin relación entre variables.O(log n) para un BST sin balance.O(1) en hashing.O acota por arriba, Ω por abajo y Θ de forma ajustada.Una función tiene un loop sobre n elementos y dentro llama array.includes, que puede recorrer m elementos. ¿Cuál es su peor caso?
O(nm). El loop externo ejecuta n veces una búsqueda que puede costar O(m). Si ambos arrays tienen el mismo tamaño, puede escribirse O(n²), pero solo bajo esa relación.