Question 1

¿Qué es la notación Big O y para qué sirve?

Accepted Answer

La notación Big O describe cómo crece el tiempo de ejecución o el uso de memoria de un algoritmo en función del tamaño de la entrada. Permite comparar algoritmos independientemente del hardware o el lenguaje de programación. Por ejemplo, O(n log n) es más eficiente que O(n²) para entradas grandes. Es fundamental en entrevistas técnicas y en el diseño de software escalable.

Question 2

¿Cuáles son las complejidades más comunes en algoritmos de ordenación?

Accepted Answer

Los algoritmos de ordenación más eficientes como Merge Sort y Heap Sort tienen complejidad O(n log n) en el caso promedio y peor caso. Quick Sort también es O(n log n) en promedio, aunque O(n²) en el peor caso. Algoritmos simples como Bubble Sort, Insertion Sort y Selection Sort son O(n²). Counting Sort y Radix Sort pueden alcanzar O(n) bajo condiciones específicas.

Question 3

¿Qué diferencia hay entre O(n) y O(log n)?

Accepted Answer

O(n) significa que el tiempo crece linealmente con el tamaño de la entrada: si la entrada se duplica, el tiempo también se duplica. O(log n) crece de forma logarítmica: si la entrada se duplica, el tiempo aumenta en una cantidad constante. La búsqueda binaria en un array ordenado es O(log n), mientras que la búsqueda lineal es O(n). Para entradas grandes, O(log n) es significativamente más rápido.

Question 4

¿Qué complejidad tienen las operaciones básicas en estructuras de datos como arrays, listas enlazadas y tablas hash?

Accepted Answer

En un array, el acceso por índice es O(1) pero la inserción o eliminación en posición arbitraria es O(n). En una lista enlazada, la inserción o eliminación al inicio es O(1), pero el acceso a un elemento por posición es O(n). Las tablas hash ofrecen búsqueda, inserción y eliminación en O(1) amortizado en el caso promedio, aunque O(n) en el peor caso por colisiones. Los árboles balanceados (BST) realizan estas operaciones en O(log n).

Question 5

¿Cómo se analiza la complejidad de un fragmento de código con bucles anidados?

Accepted Answer

Para analizar un bucle simple que recorre n elementos, la complejidad es O(n). Cuando hay dos bucles anidados, cada uno de n iteraciones, la complejidad es O(n²). Si el bucle interno no depende del externo sino que siempre recorre k elementos fijos, sigue siendo O(n). La regla general es multiplicar las complejidades de los niveles de anidamiento dependientes y sumar las de los bloques secuenciales, quedándose con el término dominante.

Notación	Nombre	Ejemplo de algoritmo	n=100 ops.
`O(1)`	Constante	Acceso a array por índice, operaciones hash	1
`O(log n)`	Logarítmica	Búsqueda binaria, BST balanceado	~7
`O(n)`	Lineal	Búsqueda lineal, recorrido de lista	100
`O(n log n)`	Lineal-logarítmica	Merge Sort, Heap Sort, Quicksort (promedio)	~700
`O(n²)`	Cuadrática	Bubble Sort, Insertion Sort, Selection Sort	10.000
`O(2ⁿ)`	Exponencial	Fibonacci recursivo, subconjuntos de un conjunto	~10³⁰

Notación	Nombre	Ejemplo de algoritmo	n=100 ops.
`O(1)`	Constante	Acceso a array por índice, operaciones hash	1
`O(log n)`	Logarítmica	Búsqueda binaria, BST balanceado	~7
`O(n)`	Lineal	Búsqueda lineal, recorrido de lista	100
`O(n log n)`	Lineal-logarítmica	Merge Sort, Heap Sort, Quicksort (promedio)	~700
`O(n²)`	Cuadrática	Bubble Sort, Insertion Sort, Selection Sort	10.000
`O(2ⁿ)`	Exponencial	Fibonacci recursivo, subconjuntos de un conjunto	~10³⁰

Quiz Complejidad Algorítmica

¿Sabes analizar algoritmos?

Complejidad Algorítmica: Conceptos Esenciales

Los 6 órdenes de complejidad más comunes

Cómo razonar la complejidad en voz alta (entrevistas)

🔗Apps relacionadas

Quiz Complejidad Algorítmica

¿Sabes analizar algoritmos?

Complejidad Algorítmica: Conceptos Esenciales

Los 6 órdenes de complejidad más comunes

Cómo razonar la complejidad en voz alta (entrevistas)

🔗Apps relacionadas

¿Sabes analizar algoritmos?

📚Complejidad Algorítmica: Conceptos Esenciales

Los 6 órdenes de complejidad más comunes

Cómo razonar la complejidad en voz alta (entrevistas)

🔗Apps relacionadas

¿Sabes analizar algoritmos?

📚Complejidad Algorítmica: Conceptos Esenciales

Los 6 órdenes de complejidad más comunes

Cómo razonar la complejidad en voz alta (entrevistas)

🔗Apps relacionadas

Complejidad Algorítmica: Conceptos Esenciales

Complejidad Algorítmica: Conceptos Esenciales