Resolver la relación de recurrencia con dos llamadas recursivas

10

Estoy estudiando el peor tiempo de ejecución de quicksort con la condición de que nunca haga una partición muy desequilibrada para diferentes definiciones de very .

Para hacer esto, me pregunto cuál sería el tiempo de ejecución en el caso de que la clasificación rápida siempre se reparta en alguna fracción modo que están en la partición izquierda y están en la partición derecha (dejando elemento, el pivote, en el medio).T(norte,pags)0 0<pags12pags(norte-1)(1-pags)(norte-1)1

No debería ser difícil ver que proporciona un límite superior para el peor de los casos donde es la partición permitida máximamente desequilibrada, ya que cualquier partición con fracción estará más equilibrada y tendrá un tiempo de ejecución menor, y No se permite ninguna fracción .T(norte,pags)pags>pags<pags

Es obvio que es el mejor caso y es el peor caso de clasificación rápida. Ambos tienen relaciones de recurrencia fáciles que se encuentran en cualquier recurso educativo. Pero no tengo idea de cómo estudiar en general. La relación obvia sería:T(norte,12)T(norte,0 0)T(n,p)

T(norte,pags)=norte+T(pags(norte-1),pags)+T((1-pags)(norte-1),pags)

Aquí me quedo atascado. Traté de buscar, pero toda la literatura que pude entender sobre los algoritmos de dividir y conquistar tomó la "división" literalmente y "engañó" el análisis utilizando el hecho de que las particiones siempre tienen el mismo tamaño, fusionando los términos en una sola vez. constante.

No sé cómo lidiar con dos llamadas recursivas, y no sé si es seguro eliminar el redondeo. ¿Es esto posible resolver analíticamente y, en caso afirmativo, cómo?

PD: No estoy interesado en los asintóticos (que es fácil de mostrar para cualquier constante ). Estoy interesado en cuánto más lento se vuelve el ordenamiento rápido a medida que hace más pequeño, por ejemplo, estoy interesado en la relación .Θ(norteIniciar sesiónnorte)pagspagsT(norte,0.25)T(norte,0,5)

PPS: Como estudiante de pregrado, me disculpo si he hecho que las cosas obvias sean demasiado extensas o no expliquen sin trivialidades. Y aunque no sé si ha sido menospreciado aquí que en otros sitios de SE, notaré que esto es de interés personal, no de tarea.

orlp
fuente

Respuestas:

9

Como mencionas, el teorema de Akra-Bazzi muestra que la solución a la recurrencia es O ( n log n ) para todo p ( 0 , 1 ) . Sin embargo, esto no revela la naturaleza de la dependencia de p . Para determinar esto último, podemos usar un enfoque de árbol de recursión.T(n,p)O(nlogn)p(0,1)p

En la raíz del árbol de recursión está el intervalo . Sus dos hijos son los intervalos { 1 , ... , p n } y { p n + 1 , ... , n } , cuya longitud total es nuevamente n . Cada uno de estos nodos tiene dos hijos (suponiendo que n sea ​​lo suficientemente grande), y así sucesivamente. Por simplicidad, ignoramos los errores de redondeo, es decir, suponemos que p n{1,n}{1,,pn}{pn+1,,n}nnpnes un entero; esto es solo un tecnicismo, y no me preocuparía por eso. Paramos el proceso cuando un nodo tiene una longitud como máximo . La complejidad del algoritmo es proporcional a la longitud total de los intervalos en el árbol. Cuando p 1 / 2 , las hojas (nodos en la que detener el proceso) tienen diferente profundidad, y que hace que sea más difícil de determinar la complejidad global.1p1/2

Podemos obtener un límite superior simple al observar que el árbol tiene como máximo niveles: cada nodo es al menos un factor de 1 - p más pequeño que su padre. Al igual que en el análisis para p = 1 / 2 , la longitud total de intervalos en cualquier nivel es como máximo n , y se obtiene un límite superior de O ( n log 1 - p ( 1 / n ) ) en el tiempo de ejecución. Desde log 1 -log1p(1/n)1pp=1/2nO(norteIniciar sesión1-pags(1/ /norte)) ylog(1-p ) - 1 =-log(1-p)=p±O( p 2 )parappequeño, podemos escribir esto comoO(nlogn / p).Iniciar sesión1-pags(1/ /norte)=Iniciar sesiónnorte/ /Iniciar sesión(1-pags)-1Iniciar sesión(1-pags)-1=-Iniciar sesión(1-pags)=pags±O(pags2)pagsO(norteIniciar sesiónnorte/ /pags)

Aquí hay un cálculo más preciso. Considere el nivel . Supongamos que no detenemos el proceso al alcanzar un pequeño intervalo. Podemos generar un vértice aleatorio tomando t pasos, en cada uno de los cuales vamos a la izquierda (por ejemplo) con probabilidad p y a la derecha (por ejemplo) con probabilidad 1 - p . Cada vez que damos un paso hacia la izquierda, el registro de la longitud del intervalo disminuye en - log p , y cada vez que damos un paso hacia la derecha disminuye en - log ( 1 - p ) . Un vértice está en el árbol real del registro de la longitud disminuida como máximo en el registro nttpags1-pags-Iniciar sesiónpags-Iniciar sesión(1-pags)Iniciar sesiónnorte. El peso total de los intervalos en el nivel del árbol es exactamente la probabilidad de que un vértice generado de acuerdo con este proceso corresponda a una disminución de, como máximo, log n . Es decir, si D es la distribución que es igual a - log p con probabilidad p y to - log ( 1 - p ) con probabilidad 1 - p , y X 1 , , X tD son independientes, entonces el peso total del nivel t estIniciar sesiónnortere-Iniciar sesiónpagspags-Iniciar sesión(1-pags)1-pagsX1,...,Xtret . Para t super-constante, la variable aleatoria X 1 + + X t se distribuye más o menos normalmente con la media [ - p log p - ( 1 - p ) log ( 1 - p ) ] t y la varianza lineal en t , entonces para t satisfactorio [ - pPr[X1++XtIniciar sesiónnorte]tX1++Xt[-pagsIniciar sesiónpags-(1-pags)Iniciar sesión(1-pags)]ttt , digamos, la probabilidad será muy cercana a 1 , mientras que para t satisface [ - p log p - ( 1 - p ) log ( 1 - p ) ] t 2 log n , digamos, estará muy cerca de cero. Definiendo[plogp(1p)log(1p)]t(logn)/21t[-pagsIniciar sesiónpags-(1-pags)Iniciar sesión(1-pags)]t2Iniciar sesiónnorte (conocida como la función de entropía binaria), concluimos que el tiempo de ejecución es Θ ( n log n / h ( p ) ) (uniforme en p , como n ). Como p 0 tenemos h ( p ) - p log ph(pags)=-pagsIniciar sesiónpags-(1-pags)Iniciar sesión(1-pags)Θ(norteIniciar sesiónnorte/ /h(pags))pagsnortepags0 0h(pags)-pagsIniciar sesiónpags, por lo que nuestra estimación anterior no fue ajustada.

Otra forma de ver el mismo análisis es tener una secuencia infinita de variables aleatorias independientes como antes, y definir un tiempo de detención T como la primera vez t tal que X 1 + + X tlog n . El tiempo de ejecución es entonces proporcional a n E [ T ] . El teorema de renovación elemental establece que lim n E [ T ] /X1,X2,...TtX1++XtIniciar sesiónnortenortemi[T] , lo que implica que el tamaño total de los intervalos es igual a ( 1 + o ( 1 ) ) n log n / h ( p ) . Más exactamente, para cada constante p el tamaño total de los intervalos es ( 1 + α p ( n ) ) n log n / h ( plimnE[T]/logn=1/E[D]=1/h(p)(1+o(1))nlogn/h(p)p , donde α p ( n ) = o ( n ) . La convergencia en el teorema de renovación elemental es exponencial en el parámetro de tiempo, log n en nuestro caso, por lo que debería ser polinomial en n , es decir, α p ( n ) = O ( n - C p ) . La convergencia también es probablemente uniforme para p ( δ , 1 - δ ) para cualquier δ > 0 .(1+αp(n))nlogn/h(p)αp(n)=o(n)lognnαp(n)=O(nCp)p(δ,1δ)δ>0


Resumiendo, la longitud total de los intervalos en el árbol de recursión, que es proporcional al tiempo de ejecución, es de la siguiente forma para cada : T ( n , p ) = ( 1 + o ( 1 ) ) n log npdondelognyh(p)=-plogp-(1-p)log(1-p)son llevados a la misma base, y elO(1)es una función dependiendo depy tendiendo a0conn.

T(n,p)=(1+o(1))nlognh(p),
lognh(p)=plogp(1p)log(1p)o(1)p0n

Además, probablemente sea cierto que para cualquier y cualquier p ( δ , 1 - δ ) es cierto que la longitud total de los intervalos tiene la forma T ( n , p ) = ( 1 + O ( n - C δ ) ) n log nδ>0p(δ,1δ)dondeCδ>0y la constante O grande oculta dependen solo deδ. En particular, debería ser el caso de que para todas las constantesp1,p2, limnT(n,p1)

T(n,p)=(1+O(nCδ))nlognh(p),
Cδ>0δp1,p2 y la convergencia es polinomialmente rápida.
limnT(n,p1)T(n,p2)=h(p2)h(p1),
Yuval Filmus
fuente
Gracias por tu rápida respuesta Yuval. Estoy un poco confundido por el hecho de que en tu resumen. h ( p ) es una constante, ¿y eso no significa que es irrelevante bajo Θ ? Decidí escribir un pequeño programa de prueba , que mostró que para n = 100000000000000 comparar T ( n , 0.1 ) / T ( n , 0.5 ) entre el método analítico y uno computacional dio un error de 0.03. Eso parece bastante grande, ¿o es de esperar? Θh(p)Θn=100000000000000T(n,0.1)/T(n,0.5)
orlp
Θpc,CpNpnNpcnlogn/h(p)T(n,p)Cnlogn/h(p)T(n,p)=(1+o(1))Cnlogn/h(p)pnpCp
lognlognnp1/h(p)
T(n,p)p1/h(p)T(1011,0.05)h(0.05)T(1011,0.4)h(0.4)
1
nω(1)