1. Clasificación:
* Sorteo de fusión: `O (n log n)` Complejidad del tiempo. Un algoritmo de división y conquista que es estable y adecuado para conjuntos de datos grandes y sin clasificar. A menudo se usa como bloque de construcción en algoritmos más complejos. Bueno para la clasificación externa (datos demasiado grandes para caber en la memoria).
* clasifica rápida: `O (n log n)` caso promedio, `o (n^2)` Peor. Otro algoritmo de división y conquista. Generalmente más rápido que la clasificación de fusiones en la práctica debido al mejor rendimiento del caché, pero más susceptible a los peores escenarios. Variaciones como la clasificación rápida aleatoria ayuda a mitigar esto.
* clasificación de montón: `O (n log n)` Complejidad del tiempo. Utiliza una estructura de datos del montón. Rendimiento garantizado `o (n log n)`, pero generalmente no tan rápido como el tipo rápido en la práctica. Clasificación en el lugar.
* radix sort: `O (NK)` Complejidad del tiempo, donde `n` es el número de elementos y` k` es la longitud de clave promedio (número de dígitos o caracteres). Un algoritmo de clasificación no basado en la comparación que es muy eficiente para tipos de datos específicos (enteros, cadenas) con una longitud de clave limitada. Puede ser más rápido que `o (n log n)` algoritmos de clasificación para datos formateados adecuadamente.
* Tim sort: `O (n log n)` Complejidad del tiempo. Un algoritmo de clasificación híbrido derivado de la clasificación de fusión y el tipo de inserción, diseñado para funcionar bien en los datos del mundo real. Utilizado como algoritmo de clasificación predeterminado en Python y Java.
2. Buscando:
* búsqueda binaria: `O (log n)` Complejidad del tiempo. Requiere que se ordenen los datos. Extremadamente eficiente para buscar en conjuntos de datos grandes y ordenados.
* Tablas de hash: `O (1)` Caso promedio de inserción, deleción y recuperación. Utiliza una función hash para mapear las teclas a los índices en una matriz. Esencial para implementar diccionarios y búsquedas en tiempo constante (en promedio). Las estrategias de resolución de colisión son importantes para manejar casos en los que diferentes claves se asignan al mismo índice.
3. Algoritmos gráficos:
* Búsqueda de amplitud (BFS): `O (V + E)` Complejidad del tiempo, donde `V` es el número de vértices y` E` es el número de bordes. Utilizado para encontrar la ruta más corta en un gráfico no ponderado, atravesando un nivel de gráfico por nivel y muchas otras tareas relacionadas con los gráficos.
* Búsqueda de profundidad (DFS): `O (V + E)` Complejidad del tiempo. Explora lo más posible a lo largo de cada rama antes de retroceder. Se utiliza para la clasificación topológica, la detección de ciclo y la resolución de problemas de laberinto.
* algoritmo de Dijkstra: `O (E log v)` Complejidad del tiempo (con una cola de prioridad implementada como un mínimo). Encuentra las rutas más cortas desde un vértice de origen hasta todos los demás vértices en un gráfico ponderado con pesos de borde no negativos.
* a* buscar: Algoritmo de búsqueda heurística que se usa ampliamente en la transferencia de rutas y el recorrido gráfico, la selección de `h (n)` impacta en gran medida su eficiencia.
* PageRank: Un algoritmo utilizado por los motores de búsqueda para clasificar las páginas web en sus resultados de búsqueda. Algoritmo iterativo que asigna un valor numérico a cada página en función del número y la calidad de los enlaces.
4. Aprendizaje automático y análisis estadístico:
* Descendencia de gradiente: Un algoritmo de optimización iterativo utilizado para encontrar el mínimo de una función. Fundamental para capacitar a muchos modelos de aprendizaje automático, incluida la regresión lineal, la regresión logística y las redes neuronales. Se utilizan variaciones como descenso de gradiente estocástico (SGD) y descenso de gradiente de mini lotes para mejorar el rendimiento.
* K-means Clustering: `O (N*k*i)` Complexidad del tiempo, donde `n` es el número de puntos de datos,` k` es el número de clústeres, y `i` es el número de iteraciones. Participa puntos de datos en clusters K basados en su proximidad a los centroides de clúster.
* Análisis de componentes principales (PCA): Reduce la dimensionalidad de los datos identificando los componentes principales (direcciones de varianza máxima). Útil para la extracción de características, reducción de ruido y visualización. La complejidad computacional depende del tamaño de la matriz de covarianza.
* Minería de reglas de asociación (por ejemplo, Apriori): Encuentra relaciones interesantes (asociaciones) entre variables en grandes conjuntos de datos. Utilizado en análisis de canasta de mercado, sistemas de recomendación y otras aplicaciones.
* Algoritmos de árbol de decisión (por ejemplo, ID3, C4.5, Cart): Utilizado para tareas de clasificación y regresión. Puede ser eficiente, pero propenso al sobreajuste.
5. Compresión de datos:
* Codificación de Huffman: `O (n log n)` Complejidad del tiempo (para construir el árbol Huffman). Un algoritmo de codificación de longitud variable utilizado para la compresión de datos sin pérdidas. Asigna códigos más cortos a caracteres/símbolos más frecuentes.
* Lempel-Ziv (LZ77, LZ78, LZW): Una familia de algoritmos de compresión de datos sin pérdidas que se usan ampliamente en formatos de archivo como ZIP y GIF. Identifique patrones de repetición en los datos y reemplácelos con códigos más cortos.
6. Procesamiento de cadenas:
* Knuth-Morris-Pratt (KMP) Algoritmo: `O (N)` Complejidad del tiempo, donde `n` es la longitud del texto. Un algoritmo de búsqueda de cadenas eficiente que encuentra ocurrencias de un patrón dentro de un texto. Evita el retroceso innecesario.
* Algoritmo de Boyer-Moore: Generalmente más rápido que KMP en la práctica, especialmente para patrones más largos. Utiliza heurísticas para omitir porciones del texto que no pueden contener el patrón.
7. Análisis numérico:
* Transformación rápida de Fourier (FFT): `O (n log n)` Complejidad del tiempo. Calcula eficientemente la transformación discreta de Fourier (DFT), que se utiliza en el procesamiento de señales, el procesamiento de imágenes y otras aplicaciones.
* Método Newton-Raphson: Un método iterativo para encontrar aproximaciones a las raíces (o ceros) de una función de valor real.
Consideraciones clave para elegir un algoritmo:
* Complejidad del tiempo: Cómo crece el tiempo de ejecución a medida que aumenta el tamaño de la entrada.
* Complejidad espacial: Cuánta memoria requiere el algoritmo.
* Características de los datos: El tipo de datos (ordenados, sin clasificar, numéricos, categóricos), su tamaño y su distribución.
* Estabilidad (para clasificar): Si el algoritmo conserva el orden relativo de elementos iguales.
* Paralelizabilidad: Si el algoritmo puede ser fácilmente paralelo para aprovechar procesadores múltiples o sistemas distribuidos.
* Complejidad de implementación: Qué difícil es el algoritmo implementarse correctamente.
* Caso de uso: La tarea específica que está tratando de lograr.
Nota importante: El algoritmo "mejor" depende del contexto específico. El perfil y la evaluación comparativa de diferentes algoritmos en sus datos reales es crucial para tomar decisiones informadas. Bibliotecas como Numpy, SciPy, Pandas (Python) y R proporcionan implementaciones altamente optimizadas de muchos de estos algoritmos, lo que facilita el aprovechamiento de las tuberías de procesamiento y análisis de datos.