8 algoritmos que los programadores deben dominar en la universidad
8 algoritmos de programación que los programadores deben dominar
Algoritmo n.º 1: algoritmo de clasificación rápida
Quick Sort es un algoritmo de clasificación desarrollado por Tony Hall. En el caso general, ordenar n elementos requiere comparaciones O(nlogn). En el peor de los casos, se requieren comparaciones O(n2), pero esto es poco común. De hecho, Quicksort es generalmente mucho más rápido que otros algoritmos O(nlogn) porque su bucle interno se puede implementar de manera eficiente en la mayoría de las arquitecturas. La clasificación rápida utiliza una estrategia de dividir y conquistar para dividir una lista en dos sublistas.
Algoritmo 2: Clasificación del montón
La clasificación del montón es un algoritmo de clasificación diseñado para utilizar la estructura de datos del montón. La clasificación de montón es una estructura que se aproxima a un árbol binario completo y satisface las propiedades de un montón: es decir, el valor clave o índice de un nodo secundario siempre es menor (o mayor) que su nodo principal. La complejidad temporal promedio de la clasificación del montón es O (nlogn).
Pasos del algoritmo:
1. Cree un montón H[0.n-1]
2. Conecte la cabeza del montón (valor máximo) con el intercambio de cola del montón
3. Reduzca el tamaño del montón en 1 y llame a shift_down (0), cuyo propósito es ajustar los datos en la parte superior de la nueva matriz a la posición apropiada. Repita el paso 2 hasta que el tamaño del montón sea 1
Algoritmo 3: Ordenación por combinación
La ordenación por combinación es un algoritmo de clasificación eficiente basado en operaciones de combinación. Este algoritmo es una aplicación muy típica de "DivideandConquer".
Pasos del algoritmo:
1. Solicite espacio para que su tamaño sea la suma de las dos secuencias ordenadas y el espacio se utilice para almacenar la secuencia fusionada.
2. Establezca dos punteros, las posiciones iniciales son las posiciones iniciales de las dos secuencias ordenadas.
3. 4. Repita el paso 3 hasta que uno de los punteros llegue al final de la secuencia. 5. Copie todos los elementos restantes de otra secuencia directamente al final de la secuencia fusionada
Algoritmo 4: Algoritmo de búsqueda binaria Algoritmo de búsqueda binaria
Es un algoritmo de búsqueda para ordenar elementos específicos en una matriz.
El proceso de búsqueda comienza desde el medio de la matriz. Si el elemento del medio es exactamente el elemento que se va a buscar, el proceso de búsqueda finaliza: si un elemento es más grande o más pequeño que el elemento del medio, entonces es. más grande o más pequeño que el elemento del medio Busque dentro de esa mitad de la matriz y comience la comparación desde el elemento del medio como lo hizo al principio. Si la matriz está vacía en algún paso, no se encontrará. Este algoritmo de búsqueda reduce el área de búsqueda a la mitad con cada comparación. Reducir la búsqueda a la mitad reduce el área de búsqueda a la mitad cada vez y la complejidad del tiempo es O (logn)
Si la matriz está vacía en un determinado paso, no se encontrará. Este algoritmo de búsqueda reduce el área de búsqueda a la mitad con cada comparación. Reducir a la mitad la búsqueda reduce el área de búsqueda a la mitad cada vez y la complejidad del tiempo es O (logn).
Algoritmo 5: BFPRT (Algoritmo de búsqueda lineal)
El problema resuelto por el algoritmo BFPRT es muy clásico, es decir, seleccionar el k-ésimo grande (k-ésimo pequeño) de una secuencia de ciertos n elementos), mediante un análisis inteligente, BFPRT puede garantizar que la complejidad del tiempo siga siendo lineal en el peor de los casos. La idea del algoritmo es similar a la de clasificación rápida. Para que el algoritmo aún sea posible en el peor de los casos. Para lograr la complejidad temporal de o (n), los autores de estos cinco algoritmos han realizado un procesamiento exquisito.
Algoritmo 6: DFS (Depth First Search)
Depth First Search (DFS) es un algoritmo de búsqueda. Atraviesa los nodos del árbol a lo largo de su profundidad y busca las ramas del árbol lo más profundamente posible. Cuando todos los bordes del nodo v hayan sido explorados por sí solos, la búsqueda volverá al nodo inicial donde se encontró el nodo v. Este proceso continúa hasta que se descubren todos los nodos a los que puede acceder el nodo de origen.
Si todavía hay nodos sin descubrir, seleccione uno de los nodos como nodo de origen y luego repita el proceso hasta que se hayan visitado todos los nodos.
La búsqueda en profundidad es un algoritmo clásico en la teoría de grafos. El uso del algoritmo de búsqueda en profundidad puede generar una tabla de clasificación topológica correspondiente al gráfico de destino. Utilizando la tabla de clasificación topológica, se pueden resolver muchos problemas relacionados con la teoría de grafos, como el problema de la ruta máxima. se puede solucionar fácilmente. Las estructuras de datos del montón se utilizan generalmente para ayudar en la implementación de algoritmos DFS.
Algoritmo 7: búsqueda en amplitud BFS
(Breadth-First-Search) es un algoritmo de búsqueda de gráficos. En pocas palabras, BFS comienza desde el nodo raíz y atraviesa los nodos del árbol (gráfico) a lo largo del ancho del árbol (gráfico). Si se visitan todos los nodos, el algoritmo termina y BFS también es una búsqueda ciega y seca. Las estructuras de datos de cola se utilizan generalmente para ayudar en la implementación de algoritmos BFS.
Pasos del algoritmo:
1. Primero, coloque el nodo raíz en la cola.
2. Tome el primer nodo de la cola y verifique si es el nodo de destino. Si se encuentra el nodo de destino, la búsqueda finaliza y se devuelven los resultados. De lo contrario, agregue a la cola todos sus hijos directos que aún no hayan sido probados.
3. Si la cola está vacía, significa que se ha verificado todo el gráfico, es decir, no hay ningún objetivo para buscar en el gráfico. Finaliza la búsqueda y devuelve el mensaje "Destino no encontrado". Repita el paso 2.
Algoritmo 8: Programación Dinámica
La programación dinámica es un método para resolver un problema dividiendo el problema original en partes más pequeñas. La programación dinámica es un método utilizado en matemáticas, informática y economía para resolver problemas complejos dividiendo el problema original en subproblemas relativamente simples. La programación dinámica suele ser adecuada para problemas con subproblemas superpuestos y subestructuras óptimas, y los métodos de programación dinámica suelen requerir mucho menos tiempo que las soluciones analíticas.
La idea básica de la programación dinámica es muy sencilla. En términos generales, para resolver un problema determinado, necesitamos resolver diferentes partes del mismo (es decir, subproblemas) y luego combinar las soluciones de los subproblemas para llegar a una solución al problema original. A menudo, muchos subproblemas son muy similares, por lo que la programación dinámica intenta reducir la cantidad de cálculo resolviendo cada subproblema solo una vez: una vez que se calcula la solución a un determinado subproblema, se memoriza y se almacena en una tabla para que usted pueda consultarla. La próxima vez que necesite una solución al mismo subproblema.