Diez algoritmos prácticos básicos que los programadores deben conocer y sus explicaciones

• ### Algoritmo 1: Algoritmo de ordenamiento rápido

La clasificación rápida es un algoritmo de clasificación desarrollado por Tony Hall. En el caso medio, la clasificación de n proyectos requiere n comparaciones. En el caso peor, requiere n comparaciones, pero esta situación no es común. De hecho, la clasificación rápida suele ser mucho más rápida que otros algoritmos, ya que su ciclo interno puede implementarse de manera eficiente en la mayoría de las arquitecturas.

La clasificación rápida utiliza la estrategia Divideandconquer para dividir una lista en dos sub-listas.

Paso del algoritmo:

• 1 Seleccione un elemento de la serie, llamado pivot,

• 1. Reordenar la matriz, todos los elementos menores que el valor de referencia se colocan en la parte delantera de la matriz, todos los elementos mayores que el valor de referencia se colocan en la parte posterior de la matriz (el mismo número puede ir a cualquier lado). Después de la salida de esta partición, la base está en la posición media de la matriz. Esto se llama operación de partición.
• 1. Recursivo (recursivo) ordena el subconjunto menor que el elemento de referencia y el subconjunto mayor que el elemento de referencia

  El caso más básico de la recursividad es que el tamaño de la serie es cero o uno, es decir, siempre se ha ordenado bien. A pesar de recurrir constantemente, este algoritmo siempre se retira, porque en cada iteración, coloca al menos un elemento en su posición final.

• ### Algoritmo 2: Algoritmo de ordenamiento de la pila

El Heapsort es un algoritmo de ordenamiento diseñado para usar esta estructura de datos. La acumulación es una estructura que se aproxima a un árbol binario completo y al mismo tiempo satisface la propiedad de la acumulación: el valor clave o el índice de un subnodo siempre es menor que (o mayor que) su nodos padres.

La complejidad en tiempo promedio de la secuencia de la pila es O{\displaystyle \mathrm {O} } nlogn) 。

Paso del algoritmo:

• 1. Crear una pila H[0..n-1]

• 2 Intercambiar el principio (el valor máximo) y el final de la pila

• 3 Reduzca el tamaño de la pila a 1 y llame shift_down () 0 para ajustar los datos de la parte superior de la nueva serie a la posición correspondiente

• 4 Repita el paso 2 hasta que el tamaño de la pila sea 1

• Algoritmo 3: Secuencia de sumisión

Mergesort es un algoritmo de clasificación eficaz basado en la operación de fusión. Este algoritmo es una aplicación muy típica de la subdivisión y la conquista.

Paso del algoritmo:

• 1. Espacio de solicitud, que tiene el tamaño de la suma de dos secuencias ya ordenadas, que se utiliza para almacenar la secuencia de la fusión
• 1. Establece dos punteros, cada uno con la posición inicial de dos secuencias ordenadas

• Comparar los elementos que apuntan los dos punteros, seleccionar el elemento más pequeño para colocarlo en el espacio de fusión y mover el puntero a la siguiente posición

• Repetir el paso 3 hasta que un indicador llegue al final de la secuencia

• 1. Copiar todos los elementos restantes de otra secuencia directamente al final de la secuencia de combinación

• Algorithm 4: algoritmo de búsqueda por división

El algoritmo de búsqueda de divisiones es un algoritmo de búsqueda que busca un elemento específico en una matriz ordenada. El proceso de búsqueda comienza en el elemento medio de la matriz, y si el elemento medio es el elemento que se busca, el proceso de búsqueda termina; si un elemento específico es mayor o menor que el elemento medio, se busca en la mitad de la matriz mayor o menor que el elemento medio, y se comienza la comparación desde el elemento medio como se comenzó. Si en un paso el número de pasos es nulo, el representante no se encuentra. Este algoritmo de búsqueda reduce el alcance de la búsqueda a la mitad en cada comparación.

• ### Algoritmo cinco: BFPRT (algoritmo de búsqueda lineal)

El BFPRT resuelve el problema clásico de seleccionar el k mayor y el k menor de una secuencia de n elementos. A través de un análisis ingenioso, el BFPRT garantiza la complejidad en tiempo lineal en el peor de los casos. La idea de este algoritmo es similar a la idea de la clasificación rápida, y, por supuesto, para que el algoritmo en el peor de los casos, todavía pueda alcanzar la complejidad en tiempo de o (n), los cinco autores del algoritmo han hecho un tratamiento refinado.

Paso del algoritmo:

• 1 Se dividen n elementos por grupo de 5, en n/5 grupos.

• 1. Saque el promedio de cada grupo, y utilice métodos de clasificación arbitrarios, como la clasificación por inserción.
• 1. El algoritmo de selección de llamada recursiva busca el promedio de todos los dígitos medios de la etapa anterior, y se establece como x, y en el caso de un número par de dígitos medios se establece como el menor de los medios.
• 1. Separar el conjunto por x, si el número menor que y igual a x es k, el número mayor que y igual a x es n-k.

• 5 , si i==k, devuelve x; si ik, recurrirá para encontrar el elemento menor de i-k en los elementos mayores de x.

  Condición de terminación: cuando n = 1, se devuelve el elemento menor i.

• Algoritmo 6: DFS (búsqueda priorizada de profundidad)

La búsqueda de profundidad es un tipo de búsqueda que recorre la profundidad de un árbol, recorriendo los nodos del árbol y buscando las ramas del árbol lo más profundamente posible. Cuando todos los lados del nodo v han sido explorados, la búsqueda regresará al nodo inicial del lado donde se encontró el nodo v. Este proceso se continúa hasta que todos los nodos que se pueden alcanzar desde el nodo de origen que se han encontrado. Si todavía hay nodos no descubiertos, se selecciona uno de ellos como nodo de origen y se repite el proceso anterior, y el proceso se repite hasta que todos los nodos se hayan visitado.

La búsqueda de prioridad de profundidad es un algoritmo clásico de la teoría gráfica. El uso de algoritmos de búsqueda de prioridad de profundidad puede generar la tabla de clasificación topográfica correspondiente a la gráfica objetivo. El uso de tablas de clasificación topográficas puede resolver fácilmente muchos problemas gráficos relacionados, como el problema de la ruta máxima, etc.

El algoritmo se ha desarrollado de la siguiente manera:

• 1 , Visita el punto v;

• 1. Empieza el recorrido en profundidad de la gráfica desde los puntos de conexión adyacentes no visitados de v, hasta que se accede a todos los vértices de la gráfica que tienen un camino en común con v;
• 1. Si aún no se ha visitado un punto en el mapa de tiempo, comience desde un punto no visitado y vuelva a hacer un recorrido de prioridad de profundidad hasta que todos los puntos del mapa hayan sido visitados.

  La descripción anterior puede ser más abstracta, por ejemplo:

  DFS comienza con un punto v en el gráfico de acceso, se inicia con v, se inicia con cualquier punto de conexión adyacente w1; se inicia con w1, se inicia con un punto de conexión adyacente a w1 pero no visitado todavía, se inicia con w2; se inicia con w2 y se inicia con un punto de conexión similar, … y así sucesivamente hasta llegar a todos los puntos de conexión adyacentes y todos los puntos de conexión visitados u.

  A continuación, retroceda un paso hacia atrás y regrese al punto que acaba de visitar la última vez para ver si hay otros puntos adyacentes que no han sido visitados. Si lo hay, visite este punto y luego inicie desde este punto una visita similar a la anterior; si no, regrese un paso más para realizar una búsqueda. Repita el proceso anterior hasta que todos los puntos del mapa de conexión hayan sido visitados.

• Algoritmo siete: BFS (Broad Foresight)

BFS es un algoritmo de búsqueda de gráficos. En pocas palabras, BFS es un algoritmo de búsqueda de gráficos que comienza en el nodo raíz y recorre el árbol a lo largo de la anchura del árbol. Si todos los nodos son visitados, el algoritmo se suspende.

Paso del algoritmo:

• 1. Coloque primero el nodo raíz en la cola.
• 1. Sacar el primer nodo de la cola y comprobar si es el objetivo.

  Si se encuentra el objetivo, finaliza la búsqueda y envía los resultados. De lo contrario, agregue a la cola todos los subnodos directos que aún no se han examinado.

• 1. Si la cola está vacía, significa que el mapa entero ha sido revisado por el cubo, es decir, que no hay ningún objetivo que se desee buscar en el mapa. Termina la búsqueda y regresa a la casilla sin encontrar el objetivo.
• 1. Repita el paso 2.

• Algoritmo ocho: el algoritmo de Dijkstra

El algoritmo de Dijkstra (en holandés: Dijkstra-salgorithm) fue propuesto por el científico holandés Eijk Dejkstra. El algoritmo de Dijkstra utiliza la búsqueda de prioridad de amplitud para resolver el problema de la fuente única de trayectorias más cortas de un gráfico de derecho no negativo. El algoritmo termina con un árbol de trayectorias más cortas. El algoritmo se utiliza a menudo en algoritmos de enrutamiento o como un submódulo de otros algoritmos gráficos.

La entrada de este algoritmo contiene un gráfico vectorial G con peso y un vértice de origen S en G. Se representa con V el conjunto de todos los vértices de G. Los lados de cada gráfico son pares de elementos ordenados formados por dos vértices.[0,∞] definición

Por lo tanto, w ((u,v) es el peso no negativo de un punto u hasta el punto v. El peso de un lado se puede imaginar como la distancia entre dos puntos. El peso de un camino entre dos puntos es la suma de los pesos de todos los lados en el camino. Se sabe que V tiene un punto s y t, y el algoritmo de Dijkstra puede encontrar el camino de menor peso de s a t.

Paso del algoritmo:

• 1, el orden inicial S={V0}, T={ resto de vértices}, el valor de la distancia correspondiente a los vértices en T Si existe , d (V0,Vi) es el peso en el arco Si no existe , entonces d (V0,Vi) es infinito.

• 1. Seleccione un punto W de T cuya distancia sea la menor y que no esté en S, y añada a S

• 3 Modificar el valor de la distancia de los vértices en el resto de T: si se agrega W como vértice medio, se acorta el valor de la distancia de V0 a Vi, y se modifica este valor de distancia

  Repetir los pasos 2 y 3 anteriores hasta que S contenga todos los vértices, es decir, W = Vi

• Algoritmo 9: Algoritmo de planificación dinámica

La programación dinámica es un método utilizado en matemáticas, ciencias de la computación y economía para resolver problemas complejos mediante la descomposición de los problemas originales en subproblemas relativamente simples. La programación dinámica se aplica a menudo a problemas con subproblemas superpuestos y propiedades de estructura óptima, y los métodos de programación dinámica suelen consumir mucho menos tiempo que las soluciones sencillas.

La idea detrás de la planificación dinámica es muy simple. En general, si queremos resolver un problema dado, necesitamos resolver sus diferentes partes (subproblemas), y luego combinar las soluciones de los subproblemas para obtener la solución del problema original. Por lo general, muchos subproblemas son muy similares, por lo que la planificación dinámica trata de resolver cada subproblema una sola vez, reduciendo así el volumen de cálculo: una vez que la solución de un subproblema dado ha sido calculada, se almacena en la memoria para que la próxima vez que se necesite resolver el mismo subproblema, se pueda consultar directamente.

El problema más clásico de la planificación dinámica es el de las mochilas.

Paso del algoritmo:

Si la solución de un subproblema que contiene la solución óptima de un problema es también la solución óptima, se dice que el problema tiene una estructura óptima (es decir, satisface el principio de optimización). La estructura óptima proporciona una pista importante para la resolución del problema con algoritmos de planificación dinámica.

La superposición de subproblemas La superposición de subproblemas se refiere a que cada subproblema generado no siempre es un problema nuevo cuando se resuelve un problema de arriba hacia abajo con un algoritmo recursivo, y algunos subproblemas se calculan repetidamente. El algoritmo de planificación dinámica utiliza esta superposición de subproblemas, que se calcula solo una vez para cada subproblema, y luego guarda sus resultados en una tabla. Cuando se necesita volver a calcular los subproblemas ya calculados, simplemente consulte los resultados en la tabla, lo que permite una mayor eficiencia.

• ### Algoritmo 10: Algoritmo de clasificación básica sencilla

El algoritmo simplista de clasificación de Bayes es un algoritmo de clasificación de probabilidad simple basado en el teorema de Bayes. La clasificación de Bayes se basa en la inferencia de probabilidad, es decir, cómo se realiza la tarea de inferencia y toma de decisiones en el caso de que la existencia de una variedad de condiciones sea incierta y solo se conozca la probabilidad de que se produzca. La inferencia de probabilidad es la correspondiente a la inferencia de certeza.

El clasificador simple de Bayes se basa en un modelo de probabilidad natural preciso, que permite obtener una clasificación muy buena en un grupo de muestras con aprendizaje supervisado. En muchas aplicaciones prácticas, los parámetros del modelo simple de Bayes se estiman utilizando el método de estimación de la máxima similitud, es decir, el modelo simple de Bayes funciona sin usar la probabilidad de Bayes o cualquier modelo de Bayes.

A pesar de estas ideas simplistas y de las suposiciones demasiado simplistas, los clasificadores básicos simplistas pueden funcionar bastante bien en muchas situaciones de realidad compleja.