Primero intentemos comprender el límite inferior de los algoritmos de clasificación y lo mejor que pueden hacer.
La ordenación es, dado un conjunto de elementos, organizarlos de manera que siga una configuración específica, generalmente en orden ascendente o descendente con números.
Combinatronics puede ver fácilmente que un conjunto de N elementos tendrá N! permutaciones en el peor de los casos.
- Dados 2n puntos en un avión. Uno quiere dibujar n segmentos que unan pares de estos puntos, de modo que no haya dos segmentos que compartan un vértice común. ¿De cuántas maneras se puede hacer esto?
- ¿Cuál era el objetivo de Pedro Domingos al escribir 'El algoritmo maestro'?
- Visión por computadora: ¿Cuáles son algunas técnicas de detección de bordes ultrarrápidas y eficientes en memoria?
- La mayoría de las definiciones / teoremas / ejemplos de privacidad diferencial que he encontrado son para consultas que devuelven un solo número por columna, como un promedio. ¿Existen mecanismos diferencialmente privados para otros tipos de consultas, como los que subconjustan filas en función de algún criterio?
- ¿Cuál es el enfoque para resolver el problema # 168 en el Proyecto Euler (por supuesto, no la fuerza bruta)?
La imagen muestra 3 elementos a ordenar, se puede ver que hay 3! = 6 permutación posible (= hojas del árbol de decisión).
Entonces, si construimos un árbol de decisión, ¡sabemos que hay al menos N! posibles respuestas que podemos obtener, es decir, hay N! hojas factoriales, ya que cada hoja es una permutación resultante del conjunto de elementos.
Como el árbol de decisión es binario (ramificación basada en un SÍ o un NO), sabemos que se puede encontrar la altura del árbol,
La altura del árbol es al menos lg (N!).
Usando la aproximación de Stirling del factorial,
http://en.wikipedia.org/wiki/Sti…
Por lo tanto, el árbol tiene una altura limitada por N lg (N) y ese es el tiempo mínimo requerido para un algoritmo de clasificación basado en comparación.
Cualquier algoritmo que tome tiempo N lg (N) es bueno. La clasificación de combinación y la clasificación de montón son algoritmos de clasificación de división y conquista de Ng (N).
Depende de dónde desea aplicar la técnica de clasificación y cuál es el comportamiento específico que exhibe el sistema donde se aplicará.
Dependiendo de la entrada y varios casos, puede haber algunos algoritmos que funcionen de manera más eficiente que otros.
Existen otras técnicas que pueden romper el límite de N lg (N) ya que no se basan en la comparación de elementos para ordenar los elementos.
Algoritmos como el conteo de conteo y el ordenamiento de Radix bajo condiciones específicas se comportan como algoritmos de ordenamiento de tiempo lineal y clasifican los elementos en tiempo O (N).
Lo anterior no se compara y solo decide la posición de los elementos en la lista ordenada simplemente mirando los elementos (y su frecuencia de aparición), de ahí el tiempo lineal.
Debe verse que funcionan dado que se conoce el rango de la entrada. Si los datos de entrada tienen elementos que varían en un intervalo grande, entonces el algoritmo puede no comportarse como lineal.
Por lo tanto, la clasificación basada en el modelo de comparación requiere al menos tiempo O (N lg (N)) mientras que otras técnicas del modelo de clasificación pueden llevar el límite a O (N).
Sugiero que el mejor algoritmo para ordenar es Heapsort, ya que se ordena en su lugar, no requiere memoria auxiliar (a diferencia de Merge sort) y no funciona O (N lg (N)). La lógica detrás de esto es bastante simple y utiliza las propiedades de una estructura de datos Heap.
