Demostrar que el tiempo previsto para ordenar $n$ está acotado por $cn \log n$ para alguna constante $c$ .
¿Podría darme algunas pistas sobre cómo puedo hacerlo?
Respuestas
¿Demasiados anuncios?
John Hughes
Puntos
27780
Es falso como se ha dicho. Por ejemplo, la ordenación radial es $O(n)$ (pero vea también la respuesta de @mlo105). Pero si se trata de comparación -basado en la clasificación, es cierto.
Una prueba (esquema): considere todas las entradas posibles del algoritmo y dibuje un árbol de ejecución, donde cada nodo interno representa una comparación y sus dos bordes de salida son las dos ramas que podrían tomarse como resultado de esa comparación, dependiendo de los datos de entrada. Una hoja de este árbol representa la terminación del algoritmo en alguna entrada posible, y se puede etiquetar con el barajado de la entrada necesario para llegar a una forma ordenada.
Porque hay $n!$ posibles salidas (correspondientes a la $n!$ formas de barajar $n$ números, por ejemplo), se tiene un árbol binario con al menos $n!$ hojas. Por lo tanto, debe tener una profundidad de al menos $log_2 (n!)$ que es $O(n \log_2 n)$ por, digamos, la aproximación de Stirling.
Oh... en cuanto al tiempo esperado, entonces se pregunta "¿Cuál es el media profundidad de un nodo en un árbol binario con $n!$ hojas?"
Bueno, no puedo responder a eso, pero puedo mostrar que es mayor que la profundidad mínima $k = \lceil n \log_2 n \rceil$ de dicho árbol.
Para cualquier hoja $A$ cuya profundidad es mayor que $k$ , toma un poco de hoja $L$ cuya profundidad es MENOR que $k$ lo sustituye por un nodo cuyo hijo izquierdo es $L$ y cuyo hijo derecho es $A$ . El resultado es un árbol cuya profundidad media no es mayor que la profundidad del que empezó, con una hoja menos de profundidad "excesiva". Repita este proceso hasta que todas las hojas tengan una profundidad no superior a $k$ . Aquí faltan detalles: se necesita, cuando un nodo no tiene más hijos, eliminarlo, y se necesita, cuando un nodo $S$ tiene un solo hijo $C$ para eliminar el nodo $S$ y hacer $C$ el hijo de $S$ de los padres.
Pero la idea es lo suficientemente clara: sólo hay que mover las cosas hacia arriba, sin aumentar la longitud media del camino a la raíz. [En el ejemplo que di, la longitud del camino para $L$ aumentó en 1, pero la longitud de la ruta para $A$ disminuyó en al menos 1, por lo que hubo una disminución neta].
ml0105
Puntos
8033
Radix Sort es interesante. En la práctica, se realiza en tiempo lineal $O(kn)$ . En teoría, es posible argumentar $k = log(n)$ , donde $n$ es el número de elementos. Supongamos que estamos considerando una matriz de $n$ elementos consecutivos. Entonces tendremos que hacer $log(n) + 1$ pasa para asegurarse de que los elementos se han clasificado correctamente. Si consideramos $1, ..., 100$ necesitamos $log_{10}(100)$ pases. Así que $k$ no es una constante arbitraria, sino que está limitada por $log(n)$ , donde $n$ es el elemento máximo de la matriz.
La ordenación binaria es la que se realiza en $\Theta(n)$ . Dado $x \in \{0, 1\}^{n}$ , sumamos $m = \sum_{i=1}^{n} x_{i}$ , luego ir a etiquetar $x_{i} = 1$ para $1 \leq i \leq m$ y $x_{i} = 0$ para $i > m$ .
Podemos escribir la ordenación binaria como un algoritmo paralelo utilizando funciones de umbral: $x_{sort}(x) = (\tau_{1}(x), \tau_{2}(x), \tau_{3}(x), ..., \tau_{n}(x))$ , donde $\tau_{k}(x)$ denota la función umbral-k (al menos $k$ bits en $x$ ).
Para mostrar el resultado, estoy de acuerdo en que la aproximación de Stirling no es necesaria. Podemos utilizar el truco de que $log(n!) \leq log(n^{n})$ para $n \in \mathbb{N}$ . Entonces, por regla de los troncos, $log(n^{n}) = n log(n)$ .
