## Resumen Un **algoritmo** es una secuencia finita de pasos para resolver un problema. La **complejidad computacional** mide cuánto tiempo (tiempo) y memoria (espacio) consume un algoritmo en función del tamaño de la entrada. La notación **Big O** es el estándar para expresar este crecimiento. Conocer la complejidad de los algoritmos permite elegir la solución más eficiente para cada problema. --- ## Puntos clave - **Big O notation:** O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) - **O(1):** constante — acceso a un elemento de un array o dict por clave - **O(log n):** logarítmico — búsqueda binaria - **O(n):** lineal — recorrer una lista - **O(n log n):** mergesort, heapsort, quicksort (caso medio) - **O(n²):** cuadrático — bubble sort, insertion sort, bucles anidados naïve - **Recursión:** función que se llama a sí misma. Requiere caso base para terminar - **Búsqueda lineal:** O(n). **Búsqueda binaria:** O(log n) — requiere lista ordenada - **Algoritmos de ordenación:** bubble sort (O(n²)), merge sort (O(n log n)), quicksort (O(n log n) medio) - **Python `sorted()`:** usa Timsort — O(n log n) en todos los casos --- ## Ejemplo práctico > ```python > # Búsqueda binaria — O(log n) > def busqueda_binaria(lista: list, objetivo: int) -> int: > izq, der = 0, len(lista) - 1 > while izq <= der: > mid = (izq + der) // 2 > if lista[mid] == objetivo: > return mid > elif lista[mid] < objetivo: > izq = mid + 1 > else: > der = mid - 1 > return -1 > > # En una lista de 1.000.000 elementos: > # Búsqueda lineal: hasta 1.000.000 comparaciones > # Búsqueda binaria: máximo 20 comparaciones (log₂ 1.000.000 ≈ 20) > ``` --- ## Esquema visual | Complejidad | Nombre | Ejemplo | n=1.000 | |---|---|---|---| | **O(1)** | Constante | Acceso dict | 1 op | | **O(log n)** | Logarítmica | Búsqueda binaria | ~10 ops | | **O(n)** | Lineal | Recorrer lista | 1.000 ops | | **O(n log n)** | Linealítmica | Merge sort | ~10.000 ops | | **O(n²)** | Cuadrática | Bubble sort | 1.000.000 ops | | **O(2ⁿ)** | Exponencial | Subconjuntos | Inviable | --- ## Mini test *El test interactivo está disponible en la sección de práctica de este bloque.* --- ## Fuentes - [Visualgo — Visualización de algoritmos](https://visualgo.net/es) - [Python Docs — Sorting HOW TO](https://docs.python.org/3/howto/sorting.html) --- ## Resumen ultra rápido - **Big O** = cota superior del crecimiento del tiempo/espacio con el tamaño de entrada. - **O(1)** = constante. **O(log n)** = binario. **O(n)** = lineal. **O(n²)** = cuadrático. - **Búsqueda binaria** = O(log n) pero requiere lista **ordenada**. - **Merge sort / Quicksort** = O(n log n). **Bubble sort** = O(n²) — evitar en producción. - **Python `sorted()`** usa Timsort = O(n log n) garantizado. - **Recursión** = caso base + llamada recursiva. Sin caso base → recursión infinita (stack overflow). - Mejor algoritmo no siempre = más rápido para n pequeña. El coste de implementación importa. --- ## Preguntas probables de examen - ¿Qué complejidad tiene la búsqueda binaria? → **O(log n)**. - ¿Qué condición requiere la búsqueda binaria? → Lista **ordenada**. - ¿Qué complejidad tienen merge sort y quicksort en el caso medio? → **O(n log n)**. - ¿Qué complejidad tiene el acceso a un elemento de un diccionario Python? → **O(1)**. - ¿Qué componentes tiene un algoritmo recursivo? → Caso base y llamada recursiva. **Errores comunes:** - Aplicar búsqueda binaria a listas no ordenadas → resultado incorrecto. - Confundir O(log n) con O(n log n): merge sort es n log n, no log n. - Olvidar el caso base en la recursión → stack overflow (RecursionError en Python). --- ## Mapa mental ```mindmap center: Algoritmos y Complejidad 📏 BIG O | O(1)

Algoritmos y complejidad computacional

Fuentes de este bloque