Recorrido narrado
La tabla completa del array ordenado
| Operación | Costo | Condición |
|---|---|---|
buscar(k) |
O(log n) | peor caso |
insertar(k, v) |
O(n) | peor caso: buscar es log n, desplazar es n |
borrar(k) |
O(n) | peor caso |
mínimo, máximo |
O(1) | siempre: están en los extremos |
rango(a, b) |
O(log n + r) | r = cantidad de resultados |
Comparado con un array sin ordenar, busca mucho más rápido y paga al insertar. La regla práctica: construir una vez, consultar muchas.
Para construirlo, no conviene insertar uno a uno: cada inserción desplaza, y el total crece como n². Se cargan todos los pares y se ordenan una vez, en O(n log n).
función construir(pares): d ← array con todos los pares ordenar(d, por clave) devolver dSu fila en la tabla de costos
Esta es la fila del array ordenado en la tabla de conjunto y diccionario, junto a la alternativa simple:
| Representación | buscar(k) |
insertar(k) |
borrar(k) |
mínimo |
sucesor(k) |
rango(a, b) con r resultados |
|---|---|---|---|---|---|---|
| array sin ordenar | O(n) | O(n) (comprobar duplicado) | O(n) | O(n) | O(n) | O(n) |
| array ordenado | O(log n) | O(n) | O(n) | O(1) | O(log n) | O(log n + r) |
Todos son costos de peor caso.
Lee el recorrido de esta página. Al pasar al siguiente momento, este cuenta como leído.