El ordenamiento rápido es un algoritmo de ordenamiento desarrollado por Tony Hall. En el caso promedio, el ordenamiento de n objetos requiere una comparación nlogn. En el peor de los casos, se requiere una comparación n2, pero esta situación es poco común. De hecho, el ordenamiento rápido es generalmente mucho más rápido que otros algoritmos de ordenamiento rápido, ya que su bucle interno se puede implementar de manera muy eficiente en la mayoría de las arquitecturas.
El ordenamiento rápido utiliza la estrategia Divideandconquer para dividir una lista en dos sublistas.
Los pasos del algoritmo:
1, elegir un elemento de la columna numérica, llamado pivote,
2, reordenar las columnas, todos los elementos menores que el valor de referencia se colocan delante de la referencia y todos los elementos mayores que el valor de referencia se colocan detrás de la referencia (el mismo número puede ir a cualquier lado). Después de salir de esta partición, la referencia se encuentra en la posición media de la columna. Esto se llama la operación de partición.
3, recurrente: ordena el subconjunto de elementos menores que el valor de referencia y el subconjunto de elementos mayores que el valor de referencia.
En el caso más básico de la recurrencia, el tamaño de la columna es cero o uno, es decir, siempre ha sido ordenado bien. Aunque sigue recurriendo, este algoritmo siempre se retira, ya que en cada iteración, pone al menos un elemento en su posición final.
Heapsort es un algoritmo de ordenamiento diseñado para utilizar esta estructura de datos. La pila es una estructura de árbol binario casi completo que satisface al mismo tiempo las propiedades de la pila: el valor de la clave o índice de un subnodo es siempre menor que (o mayor que) su nodo padre.
La complejidad de tiempo promedio de la ordenación de la pila es O (nlogn).
Los pasos del algoritmo:
1, crear una pila H [0...n-1]
2, sustituye el principio (max) y el final de la pila
3, reducir el tamaño de la pila a 1 y llamar Shift_down ((0), con el fin de ajustar los datos de la nueva parte superior de la matriz a la posición correspondiente
4, repita el paso 2 hasta que el tamaño de la pila sea 1.
Mergesort es un algoritmo de clasificación eficaz basado en operaciones de agregación. Este algoritmo es una aplicación muy típica de la división y conquista.
Los pasos del algoritmo:
1, el espacio de solicitud, que tiene el tamaño de la suma de dos secuencias ordenadas, que se utiliza para almacenar las secuencias fusionadas
2, establece dos puntos de partida, con la posición inicial de cada uno de los dos puntos de partida de la secuencia ordenada
3. Compare los elementos a los que apuntan los dos punteros, seleccione el elemento relativamente pequeño para colocarlo en el espacio combinado y mueva el puntero a la siguiente posición.
4, repita el paso 3 hasta que un puntero llegue al final de la secuencia.
5, copiando todos los elementos restantes de otra secuencia directamente a la cola de la secuencia combinada
Un algoritmo de búsqueda binaria es un algoritmo de búsqueda de un elemento específico en una matriz ordenada. El proceso de búsqueda comienza en el elemento medio de la matriz y termina si el elemento intermedio es el elemento que se busca; si un elemento específico es mayor o menor que el elemento intermedio, se busca en la mitad de la matriz que es mayor o menor que el elemento intermedio, y se compara desde el elemento intermedio como al principio.
El BFPRT resuelve el problema clásico de elegir el k mayor (k menor) elemento de una serie de n elementos, y mediante un análisis ingenioso, garantiza que el BFPRT sigue siendo de complejidad en tiempo lineal en el peor de los casos. La idea del algoritmo es similar a la idea de ordenar rápidamente, por supuesto, para que el algoritmo pueda alcanzar la complejidad en tiempo de o (n) en el peor de los casos, los cinco autores del algoritmo han hecho un trabajo ingenioso.
Los pasos del algoritmo:
1, dividir n elementos en grupos de 5 por grupo, divididos en grupos de n / 5 (por encima del límite).
2, extraer la mediana de cada grupo, cualquier método de ordenamiento, por ejemplo, insertar ordenamiento.
El algoritmo de selección de llamada recurrente busca el mediano de todos los medianos en el paso anterior, y se establece como x, en el caso de medianos pares, se establece como elegir el menor del medio.
4, para dividir la matriz con x, el número de individuos menores que x es igual a k, y el número de individuos mayores que x es n - k.
5, si i == k, regresa x; si i < k, recurre para encontrar el elemento menor que i en el elemento menor que x; si i > k, recurre para encontrar el elemento menor que i en el elemento mayor que x.
Condición de terminación: cuando n = 1, se devuelve el elemento pequeño i.
El algoritmo de búsqueda profunda-primera es un algoritmo de búsqueda que recorre los nodos del árbol a lo largo de la profundidad del árbol y se ramifica lo más profundamente posible. Cuando todos los lados del nodo v han sido explorados, la búsqueda se remonta al punto de inicio del lado del nodo v encontrado. El proceso continúa hasta que todos los nodos que se han encontrado y que pueden ser alcanzados desde el nodo de origen. Si no existe un nodo encontrado, se selecciona uno de ellos como nodo de origen y se repite el proceso hasta que todos los nodos sean visitados.
La búsqueda de prioridad profunda es un algoritmo clásico en la teoría de gráficos, que permite generar tablas de ordenamiento topográfico correspondientes a las tablas de destino. La utilización de tablas de ordenamiento topográfico permite resolver fácilmente muchos problemas gráficos relacionados, como el problema del camino máximo, etc.
En profundidad, el paso a paso de los algoritmos es prioritario:
1, acceso a la cima v;
2, a partir de los puntos adyacentes no visitados de v, se recorre el gráfico con prioridad de profundidad; se accede a todos los picos del gráfico que se encuentran en el mismo camino que v;
3. Si todavía hay puntos no visitados en el gráfico, vuelve a recorrer la prioridad de profundidad a partir de un punto no visitado hasta que todos los puntos del gráfico hayan sido visitados.
La descripción anterior puede ser más abstracta, por ejemplo:
DFS comienza con un vértice v en una de las gráficas de acceso, parte de v, accede a cualquiera de sus vértices adyacentes w1; luego parte de w1, accede a un vértice w2 adyacente a w1 pero que aún no ha sido visitado; luego parte de w2, realiza una visita similar,... y así sucesivamente, hasta llegar a un vértice u donde todos los vértices adyacentes han sido visitados.
Luego, retroceda un paso y vuelva al tope que visitó la última vez para ver si hay otros tópicos adyacentes que no fueron visitados. Si es así, visite este tope y luego siga adelante desde este tope para realizar una visita similar a la anterior; si no, vuelva a este paso y busque. Repita el proceso hasta que se hayan visitado todos los tópicos en el mapa de conexiones.
Breadth-First-Search es un algoritmo de búsqueda gráfica. En pocas palabras, BFS es un algoritmo de búsqueda gráfica que recorre los nodos del árbol a lo largo del ancho del árbol, comenzando por el nodo raíz. Si todos los nodos son visitados, el algoritmo se detiene.
Los pasos del algoritmo:
1, primero coloca el nodo raíz en la cola.
2, extrae el primer nodo de la cola y comprueba si es el objetivo.
Si se encuentra el objetivo, se termina la búsqueda y se devuelven los resultados. De lo contrario, añadirá a la cola todos los subnodos directos que no haya examinado.
3. Si la cola está vacía, indica que se ha revisado el cuadro entero y que no se desea buscar ningún objetivo en el cuadro.
Repetir el paso 2.
El algoritmo de Dijkstra fue propuesto por el científico informático holandés Eijker Dijkstra. Dijkstra utiliza una búsqueda de prioridad de ancho para resolver el problema del camino más corto de un solo origen de un gráfico orientado no negativo, y el algoritmo termina obteniendo 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 del algoritmo contiene un gráfico orientado ponderado G, y un vértice de origen S en G. V representa el conjunto de todos los vértices de G. Cada lado del gráfico es un par de elementos ordenados formados por dos vértices. U, v indica que hay un camino que va desde el vértice u hasta v. E representa el conjunto de todos los lados de G, y el peso del lado está definido por la función de peso w: E→[0,∞].
Por lo tanto, w (u, v) es el peso no negativo del punto u al punto v. El peso del lado se puede imaginar como la distancia entre los dos puntos. El peso del camino entre los dos puntos es la suma de los pesos de todos los lados del camino. Se sabe que hay puntos s y t en V, y el algoritmo de Dijkstra puede encontrar el camino de menor peso de s a t. Por ejemplo, el camino más corto.
Los pasos del algoritmo:
1, el valor de la distancia correspondiente a los puntos máximos en T, cuando S = {V0}, T = {residuos de los puntos máximos}
Si existe
2, Seleccione un punto W de T cuyo valor de distancia sea el menor y que no esté en S, y agregue S
3, modificación del valor de la distancia entre los puntos de la parte media de T: si se añade W como punto medio, se reduce el valor de la distancia de V0 a Vi, modificando este valor de la distancia
Repita los pasos 2 y 3 hasta que S incluya todos los vértices, es decir, W = Vi.
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 problemas secundarios relativamente simples. La programación dinámica se aplica a menudo a problemas con superposición subproblemática y propiedades estructurales de los componentes óptimos, y suele llevar mucho menos tiempo que una solución simple.
La idea básica detrás de la programación dinámica es muy simple. En general, para resolver un problema dado, necesitamos resolver sus diferentes partes ("problemas de subconjuntos") y resolver subproblemas de recombinación para resolver el problema original. A menudo, muchos subproblemas son muy similares, por lo que la programación dinámica intenta resolver cada subproblemas una sola vez, lo que reduce el volumen de cálculo: una vez que se ha resuelto un subproblemas dado, se almacena en memoria para que se pueda consultar directamente la próxima vez que se necesite resolver el mismo subproblemas.
El problema más clásico de la planificación dinámica es el de la mochila.
Los pasos del algoritmo:
1, propiedades estructurales óptimas. Si la solución del problema que contiene la solución óptima es también óptima, se dice que el problema tiene propiedades estructurales óptimas (es decir, cumple con los principios de optimización).
La superposición de los subproblemas se refiere a la superposición de los subproblemas que no son siempre nuevos cada vez que se resuelven los problemas de arriba hacia abajo con algoritmos recursivos, y algunos subproblemas se computan varias veces. Los algoritmos de planificación dinámica aprovechan esta superposición de los subproblemas, computan cada subproblemas una sola vez y luego guardan sus resultados en una tabla. Cuando se necesita volver a calcular los subproblemas ya calculados, simplemente mirar el resultado en la tabla para obtener una mayor eficiencia.
El algoritmo de clasificación básica de Bayes es un algoritmo de clasificación de probabilidades simple basado en el teorema de Bayes. La base de la clasificación básica de Bayes es el razonamiento de probabilidades, es decir, cómo realizar tareas de razonamiento y decisión en condiciones de incertidumbre, solo con la posibilidad de que se produzcan. El razonamiento de probabilidades corresponde al razonamiento de certeza.
Los clasificadores de Bayes primitivos se basan en modelos de probabilidad natural precisos y obtienen muy buenos resultados de clasificación en conjuntos de muestras con aprendizaje supervisado. En muchas aplicaciones prácticas, los parámetros de los estimadores de Bayes primitivos se estiman con el método de estimación de máxima similitud, en otras palabras, los modelos de Bayes primitivos funcionan sin el uso de probabilidades de Bayes o de ningún modelo de Bayes.
A pesar de estas ideas y supuestos simplistas, los clasificadores Bayesian primitivos pueden funcionar bastante bien en muchas situaciones de realidad complejas.