Análisis de Algoritmos Comunes

✅ Objetivo:
Entender cómo diferentes algoritmos procesan los datos, cuánto tiempo tardan y cuánta memoria consumen.

1. Búsqueda en un Array #

Cuando queremos encontrar un elemento en un array, tenemos dos estrategias:

Búsqueda Lineal (O(n)) #

Si el array no está ordenado, la única opción es revisar uno por uno hasta encontrar el elemento.

📌 Ejemplo: Búsqueda Lineal

✅ Análisis:

• Complejidad temporal: O(n), ya que en el peor caso recorremos todo el array.
• Complejidad espacial: O(1), ya que no usamos memoria extra.

Búsqueda Binaria (O(log n)) #

Si el array está ordenado, podemos usar búsqueda binaria, que divide el problema a la mitad en cada paso.

📌 Ejemplo: Búsqueda Binaria

✅ Análisis:

• Complejidad temporal: O(log n), ya que descartamos la mitad en cada paso.
• Complejidad espacial: O(1), no usamos memoria extra.

📌 Conclusión:

• Si el array no está ordenado, usamos búsqueda lineal (O(n)).
• Si el array está ordenado, usamos búsqueda binaria (O(log n), mucho más rápida).

2. Algoritmos de Ordenación #

Los algoritmos de ordenación organizan los datos de menor a mayor o de mayor a menor.

Bubble Sort (O(n²)) #

Uno de los algoritmos más simples, pero ineficiente para listas grandes.

📌 Ejemplo: Bubble Sort

✅ Análisis:

• Complejidad temporal: O(n²), ya que comparamos todos los pares posibles.
• Complejidad espacial: O(1), ya que ordenamos en el mismo array.

📌 Conclusión:

• No usar en listas grandes.
• Más eficientes: QuickSort o MergeSort.

Merge Sort (O(n log n)) #

Un algoritmo eficiente basado en Divide y Vencerás.

📌 Ejemplo: Merge Sort

✅ Análisis:

• Complejidad temporal: O(n log n), ya que dividimos log n veces y combinamos O(n).
• Complejidad espacial: O(n), ya que creamos nuevos arrays.

📌 Conclusión:

• Merge Sort es más eficiente que Bubble Sort.
• En la práctica, QuickSort es aún más rápido en la mayoría de los casos.

QuickSort (O(n log n)) #

Un algoritmo eficiente basado en Divide y Vencerás.

📌 Ejemplo: Merge Sort

✅ Análisis:

• Complejidad temporal:

  • Peor caso (array ya ordenado y mal pivote): O(n²)
  • Mejor caso (pivote óptimo): O(n log n)
  • Caso promedio: O(n log n)

• Complejidad espacial:

  • O(log n) en el mejor caso y caso promedio si se usa la versión in-place (que particiona el array sin usar listas auxiliares).
  • O(n) en el peor caso si se usa una versión con listas auxiliares.

📌 Conclusión:

• En la práctica, QuickSort es aún más rápido en la mayoría de los casos.

3. Algoritmos Recursivos y Complejidad #

Los algoritmos recursivos llaman a sí mismos para resolver subproblemas más pequeños.

Fibonacci Recursivo (O(2ⁿ)) #

📌 Ejemplo: Fibonacci sin optimización

✅ Análisis:

• Complejidad temporal: O(2ⁿ), extremadamente lento.
• Complejidad espacial: O(n), por la pila de recursión.

📌 Solución: Usar memorización (Programación Dinámica) para evitar cálculos repetidos.

✅ Análisis:

• Complejidad temporal: O(n), mejor que O(2ⁿ).
• Complejidad espacial: O(n), por la memoria usada.

4. 4. Resumen de Complejidades #