Basta con leer ciclos y funciones sencillas. No necesitas saber cálculo: compararás cómo crece el trabajo al aumentar n.
CONTENIDO ORIGINAL
Avanza en orden. Cada lección está redactada para Palta es Cool, utiliza ejemplos propios y termina con una actividad cuya respuesta puedes desplegar.
ANTES DE EMPEZAR
Ubícate antes de avanzar
Al terminar deberías poder relacionar Tiempo y espacio con Big O y resolver un caso nuevo.
Reserva entre 75 y 120 minutos o divide el laboratorio en dos sesiones.
04 / PREPARA EL LABORATORIO
Instala un JDK actual y utiliza un editor o IDE con soporte para Java. Trabaja en un proyecto de laboratorio separado.
Abrir la guía de herramientas →Diagnóstico rápido: ¿cómo se relacionan Tiempo y espacio y Big O? ＋
No necesitas acertar todavía. Escribe una hipótesis de dos líneas y compárala con tu respuesta al finalizar; si puedes corregirla y justificar el cambio, hubo aprendizaje.
Aprende el tema paso a paso
Compararás algoritmos por su crecimiento y no por una medición aislada, manteniendo visibles tiempo, memoria y supuestos.
Al terminar podrás
- La complejidad empieza definiendo qué crece
- Big O permite descartar estrategias que no escalan
- Tiempo, espacio y amortización cuentan historias distintas
01
Entrada y operación
La complejidad empieza definiendo qué crece
Antes de contar, define n y la operación relevante. Una sentencia dentro de un ciclo de n iteraciones crece linealmente; dos ciclos anidados que recorren toda la entrada suelen producir n². Constantes y términos menores se omiten al describir crecimiento asintótico.
n debe tener significado concreto.
Cuenta la operación dominante.
Separa mejor, promedio y peor caso cuando cambian la decisión.
¿O(n) significa exactamente n milisegundos?
Mostrar respuesta ＋
No. Describe cómo crece el trabajo con n; no fija una unidad ni un tiempo exacto.
02
Órdenes de crecimiento
Big O permite descartar estrategias que no escalan
O(1), O(log n), O(n), O(n log n), O(n²) y O(2ⁿ) representan familias de crecimiento. Para entradas pequeñas, una constante grande puede dominar; para tamaños altos, el orden suele importar más. La notación no reemplaza medir una implementación real.
Acceso a un índice de arreglo: O(1).
Búsqueda binaria: O(log n) si los datos están ordenados.
Comparar todos los pares: O(n²).
¿Por qué una solución O(n) no es automáticamente mejor?
Mostrar respuesta ＋
Puede usar demasiada memoria, tener constantes grandes o depender de supuestos que no cumple la entrada. La elección incluye restricciones reales.
03
Costo total
Tiempo, espacio y amortización cuentan historias distintas
Un arreglo dinámico suele agregar al final en O(1) amortizado: algunas ampliaciones cuestan O(n), pero ese costo se reparte entre muchas inserciones. La complejidad espacial incluye la estructura, referencias y memoria auxiliar. Medir exige calentar el entorno, repetir y conservar la misma entrada.
Amortizado no significa que cada operación cueste lo mismo.
Una referencia también ocupa espacio.
La comparación experimental cambia una variable a la vez.
¿Cuál es el costo de la inserción exacta que provoca una ampliación?
Mostrar respuesta ＋
Es O(n) por copiar los elementos; el costo promedio sobre una secuencia de inserciones es O(1) amortizado.
Tu recorrido en tres ideas
- La complejidad empieza definiendo qué crece
- Big O permite descartar estrategias que no escalan
- Tiempo, espacio y amortización cuentan historias distintas
Compara tres detectores de duplicados
Une análisis asintótico, medición, memoria y distribución de entradas para evitar conclusiones basadas en una sola ejecución.
CASO
Debes procesar desde cien hasta un millón de identificadores, pero algunas ejecuciones tienen poca memoria.
Procedimiento
- Implementa comparación por pares, ordenamiento y conjunto con la misma semántica.
- Genera entradas sin duplicados y con repetición temprana y tardía.
- Mide tiempo y memoria, contrasta con Big O y recomienda según la restricción.
Evidencia mínima
- Definición de n y casos de entrada.
- Tabla o curva con repeticiones y entorno.
- Resultado idéntico y explicación de cada crecimiento.
Mostrar razonamiento modelo ＋
La solución cuadrática puede terminar temprano en un caso favorable, pero escala mal sin duplicados. El conjunto suele ser lineal esperado y usa memoria; ordenar cuesta O(n log n) y puede ser preferible si permite trabajar sobre la misma colección.
Para ir más lejos¿Cómo cambiaría la estrategia si los datos no caben en memoria?
CIERRE DE LA SECCIÓN
Comprueba que puedes usarlo
Antes de continuar, revisa estos tropiezos frecuentes y resuelve un caso sin copiar los ejemplos.
Confundir Big O con un tiempo exacto.
Informar solo tiempo e ignorar memoria, peor caso y supuestos.
Ahora hazlo sin guía
Compara tres estrategias para detectar duplicados: pares, ordenar y conjunto.
Mostrar pauta de corrección ＋
Una respuesta sólida:
- Define n y la operación dominante.
- Incluye tiempo y espacio.
- Justifica una elección para dos restricciones distintas.