algorithm - ordenamiento - ordenar numeros en java netbeans
algoritmo-¿Cómo ordenar una matriz 0/1 con 2n/3 comparaciones? (2)
"0 o 1 con igual probabilidad" es la condición para el caso "promedio". Otros casos pueden tener peor momento.
Sugerencia 1: 2/3 = 1/2 + 1/8 + 1/32 + 1/128 + ...
Sugerencia 2: considere la secuencia como una secuencia de pares y compare los elementos de cada par. La mitad volverá igual; la mitad no lo hará De la mitad que es desigual, usted sabe qué artículo en el par es 0 y cuál es 1, por lo que no necesitan más comparaciones.
En el Manual de Diseño de Algoritmos , hay tal especial
4-26 Considere el problema de clasificar una secuencia de n 0 y 1 usando comparaciones. Para cada comparación de dos valores x e y, el algoritmo aprende cuál de x <y, x = y, o x> y tiene.
(a) Dé un algoritmo para clasificar en n - 1 comparaciones en el peor de los casos. Demuestra que tu algoritmo es óptimo.
(b) Dé un algoritmo para clasificar 2n / 3 comparaciones en el caso promedio (suponiendo que cada una de las n entradas es 0 o 1 con igual probabilidad). Demuestra que tu algoritmo es óptimo.
Para (a), creo que es bastante fácil. Puedo elegir un [n-1] como pivote, luego hacer algo como en una partición de orden rápida, escanear 0 a n - 2, encontrar el punto medio donde el lado izquierdo es todo 0 y el lado derecho es todo 1, esto toma comparaciones n - 1 .
Pero para (b), no puedo obtener una pista. Dice "cada una de las n entradas es 0 o 1 con igual probabilidad" , así que supongo que puedo asumir que los números de 0 y 1 son iguales? Pero, ¿cómo puedo obtener un resultado relacionado con 1/3? dividir toda la matriz en 3 grupos?
Gracias
No, significa que en cualquier posición, tiene la misma probabilidad (probabilidad) de que el valor de entrada sea 0 o 1. Esto le da una primera pista: su algoritmo será aleatorio.
El tiempo de ejecución dependerá de alguna variable aleatoria, y debe tomar el valor esperado para obtener el caso de complejidad promedio . Tenga en cuenta que en este caso, debe detallar durante el análisis de complejidad, ya que requieren una constante precisa ( 2/3n lugar de simplemente O(n) )
Editar:
Sugerencia En la matriz ordenada (la que se obtiene al final), es lo único que varía, sabiendo que solo tiene 2 elementos posibles.