Análisis del algoritmo de clasificación en una lista de 0 y 1 elemento.

Estoy tratando de entender la diferencia que haría si los siguientes algoritmos de clasificación recibieran un conjunto de entradas binarias, es decir, una colección de 0 y 1 solamente.

a) Heapsort b) Quicksort c) MergeSort d) Clasificación por inserción.

Estoy buscando la diferencia en el número de comparación requerida para ordenar la lista.

Pregunta exacta: cómo la restricción del elemento 0 y 1 puede afectar el número total de comparaciones realizadas y dar el límite \theta resultante. En mi perspectiva, no habrá ningún cambio en MergeSort e Insertion sort, ya que requerirían el mismo número de comparación.

Sin embargo, en un pensamiento muy diferente, estoy pensando que si conocemos los datos (es decir, son 0 o 1), ¡entonces en el árbol de decisión no habrá n! salidas factoriales. Como podemos reducirlo a unos pocos menos, no estoy seguro acerca de este pensamiento del árbol de decisión . Por favor proporcione sus pensamientos sobre esto.

Nota al margen: la ordenación por conteo ordenaría una matriz de este tipo en O ( norte ) . en.wikipedia.org/wiki/Counting_sort
¿Ha considerado preguntar esto en el sitio beta de computerScience.SE?
No, no conozco este sitio web. ¿Puedes darme la URL exacta? (computerScience.se no carga)

Respuestas (2)

Mergesort es un algoritmo ajeno , lo que quiere decir que realizará los mismos pasos (excepto los involucrados en la fusión) para cada secuencia de entrada, por lo que sus tiempos promedio y en el peor de los casos serán Θ ( norte registro ⁡ norte ) en entradas restringidas a 0 / 1 secuencias.

La ordenación por inserción se vuelve interesante para sus entradas, pero no es demasiado difícil ver que el tiempo de ejecución en el peor de los casos seguirá siendo O ( norte 2 ) : Mire la cantidad de intercambios que se tendrán que hacer en la entrada ⟨ 1 , 0 , 1 , 0 , … , 1 , 0 ⟩ . El rendimiento promedio es, como de costumbre, más complicado y no estoy listo para reclamar ningún resultado por eso.

Quicksort es aún más interesante, ya que la primera llamada a la partición dejará la matriz ordenada después O ( norte ) permutas Si QS se escribiera con eso en mente, entonces su comportamiento cambiaría de O ( norte registro ⁡ norte ) en promedio (o O ( norte 2 ) en el peor de los casos) a O ( norte ) . Si no se identificara este hecho, luego de la primera partición, las subsiguientes dividirían cada subarreglo en dos partes, una que contiene un solo elemento y la otra que contiene todo el resto, lo que lleva a O ( norte 2 ) desempeño tanto en el promedio como en el peor de los casos.

¡Ups! Me acabo de dar cuenta de que heapsort también estaba en tu lista. Tendré que volver a hablar contigo sobre eso.

Gracias por su respuesta. :) Yo también obtuve un resultado algo similar, pero no estaba seguro de si eran correctos o no. Aquí están mis resultados: Clasificación de inserción: theta (n ^ 2), si no. de 1 o 0 son constantes, entonces es theta(n) Merge Sort: theta(nlogn), No cambia incluso si los 1 o 0 son constantes. Heapsort: theta(nlogn), si no. de 1 son constantes entonces theta(nlogn). Si no. de 0 son constantes entonces theta(n). QuickSort: theta(n^2), Sin cambios si no. de 0 o 1 son constantes.

Mejor caso = datos ya ordenados Caso promedio = algunos datos ordenados, algunos datos sin ordenar. Peor caso = datos totalmente desordenados

Ordenar por combinación: Mejor = NlogN , AVE=NlogN, PEOR = NlogN

Clasificación por inserción = Mejor = N , PROMEDIO = N^2, PEOR = N^2

Quicksort = NlogN , AVE=NlogN, PEOR = N^2

Conozco estas fórmulas, quiero saber qué diferencia haría con los valores de entrada entre 0 y 1 solamente. ¿Habría algún cambio en el límite theta de estos algoritmos? Creo que habrá algunos, pero no puedo encontrar la forma adecuada de averiguarlo.
Análisis del algoritmo de clasificación en una lista de 0 y 1 elemento.
RespuestasAquíPolítica de privacidad1y, 0v