¿Un ejemplo de un algoritmo de nivel principiante, un algoritmo de nivel intermedio y un algoritmo de nivel complejo / experto?

7

Me gustaría tener una idea del rango de complejidad en el que se encuentran los algoritmos. Creo que sería interesante y útil para quienes, como yo, tratar de comprender mejor cómo se formulan los algoritmos y cómo deconstruirlos.

¿Puede ofrecer un algoritmo básico con una explicación, un algoritmo intermedio con una explicación y quizás un experto de nivel uno (con o sin) una explicación?

    
pregunta zkidd 13.12.2010 - 17:03

3 respuestas

17

De la Matriz de competencia del programador:

Principiante
clasificación básica, búsqueda y estructura de datos transversal y algoritmos de recuperación

Intermedio
Tree y Graph estructuras de datos, simples greedy y divide y conquista los algoritmos.

Avanzado
algoritmos de gráficos , algoritmos de computación numérica , etc.

    
respondido por el Robert Harvey 13.12.2010 - 17:18
8

Principiante

Búsqueda binaria : localiza la posición de un elemento en una matriz ordenada.

Inserción de árbol AVL : inserte un elemento en un árbol AVL manteniendo la propiedad de equilibrio de subárbol.

Búsqueda en profundidad primero , Búsqueda de Breadth-first : recorra los nodos de un gráfico en orden DFS o BFS.

Intermedio

Algoritmo de Dijkstra : algoritmo de búsqueda gráfica que resuelve el problema de la ruta más corta de una sola fuente para una gráfica con borde no negativo costos de ruta, produciendo un árbol de ruta más corto.

Subsequence más largo común : encuentre la subsecuencia más larga común a todas las secuencias en un conjunto de secuencias (a menudo solo dos).

Casco convexo (Escaneo Graham) : dado un conjunto de puntos, encuentre el subconjunto mínimo de esos puntos para cubrirlos un polígono convexo.

Sorting Sort : algoritmo de clasificación de enteros consecutivos en O (n).

Avanzado

Consulta de rango mínimo : dada una matriz A [1, n] de n objetos ordenados (como números), una Consulta de rango mínimo (o RMQ) de i a j solicita la posición de un elemento mínimo en la sub-matriz A [i, j]. Las RMQ se pueden utilizar para resolver el problema ancestro común más bajo .

    
respondido por el vz0 13.12.2010 - 17:43
5

Algunos ejemplos más

Principiante: Reversión de la lista vinculada , Mergesort , Tamiz de Eratóstenes , Red- algoritmos de árbol rojo (inserción y eliminación)

Intermedio: Simplex , Prueba de primalidad de Miller-Rabin , codificación Huffman , algoritmo de Kruskal

Avanzado: Algoritmo Viterbi , Cooley – Tukey FFT , Recocido simulado , inferencia de tipo Hindley-Milner

Intenté encontrar enlaces que tuvieran al menos algún pseudocódigo y / o una buena explicación. Pero lo que pasa con los algoritmos avanzados es que tienen muchas variaciones. Entonces, puedes explicar el esquema básico de un "algoritmo genético", pero en realidad hay muchos algoritmos con ese nombre. (Lo mismo para la FFT; vinculé una variante con nombre)

Este texto sobre integración numérica , para una audiencia de juegos, describe dos algoritmos para la integración numérica: uno más sencillo , un algoritmo sencillo (el integrador de Euler) y uno más avanzado (el integrador de orden 4 de Runge-Kutta). Puede ser bueno para ver "básico contra avanzado". Puede utilizar integradores para simular la física, y el integrador de Euler conduce a errores enormes, por lo que recomienda RK4 en su lugar. Pero son posiblemente variaciones del "mismo" algoritmo: Euler es RK de primer orden.

    
respondido por el elias 11.12.2011 - 05:04

Lea otras preguntas en las etiquetas