Intentando entender las comparaciones 2N lnN para quicksort

13

Estaba analizando Quicksort en el libro de algoritmos de Sedgewick. Crea la siguiente relación de recurrencia para el número de comparaciones en el ordenamiento rápido al ordenar una matriz de N elementos distintos.

Me está costando entender esto ... Sé que se necesita 1 / N de probabilidad para que cualquier elemento se convierta en el pivote y que si k se convierte en el pivote, la sub-matriz izquierda tendrá elementos k-1 y la sub-matriz derecha tendrá elementos Nk.

1.¿Cómo se convierte N + 1 en el costo de la partición? ¿Se necesita N + 1 para hacer la partición?

2.Sedgewick dice que, para cada valor de k, si los sumas, la probabilidad de que el elemento de partición sea k + el costo de los dos subarreglos, obtienes la ecuación anterior.

  • ¿Puede alguien explicar esto para que aquellos con menos conocimientos de matemáticas (yo) puedan entender?
  • Específicamente, ¿cómo obtienes el segundo término en la ecuación?
  • ¿Qué significa exactamente ese término?
pregunta damon 11.07.2013 - 12:36

2 respuestas

7

La función de costo C para quicksort consta de dos partes. La primera parte es el costo de la partición de la matriz en dos "mitades" (las mitades no tienen que ser del mismo tamaño, de ahí las comillas). La segunda parte es el costo de clasificar esas dos mitades.

  1. El término (N + 1) es en realidad un término condensado, y proviene de los términos

    (N - 1) + 2
    

    Este es el costo de la partición en quicksort: N-1 se compara con el valor de pivote, y 2 comparaciones adicionales debido a algunas condiciones de contorno en la partición.

  2. La segunda parte de la ecuación consiste en los costos para clasificar las dos 'mitades' a cada lado del valor pivote k .

    Después de elegir un valor pivote, te quedan dos "mitades" sin clasificar. El costo de clasificar estas 'mitades' depende de su tamaño y se describe más fácilmente como una aplicación recursiva de la función de costo C . Si el pivote es el menor de los valores de N , los costos para clasificar cada una de las dos 'mitades' son respectivamente C(0) y C(N-1) (el costo para clasificar una matriz con 0 elementos y el costo para clasificar una con N-1 elementos). Si el pivote es el quinto más pequeño, entonces el costo para clasificar cada una de las dos 'mitades' es, respectivamente, C(5) y C(N-6) (el costo para clasificar una matriz con 5 elementos y el costo para clasificar una con N-6 elementos). Y de manera similar para todos los demás valores de pivote.

    ¿Pero cuánto cuesta ordenar esas dos 'mitades' si no conoce el valor de pivote? Esto se hace tomando el costo de cada valor posible del pivote y multiplicándolo por la posibilidad de que ese valor en particular aparezca.

    Como cada valor de pivote es igual de probable, la posibilidad de elegir un valor de pivote particular es 1/N si tiene elementos N . Para entender esto, piensa en lanzar un dado. Con un dado adecuado, la probabilidad de que cada lado termine mirando hacia arriba es igual, por lo que la posibilidad de tirar un 1 es 1/6.

    Combinado, esto da el término de suma donde, para cada valor posible k del pivote, el costo ( C(k-1) + C(N-k) ) se multiplica por la posibilidad ( 1/N )

  3. La derivación adicional de la fórmula de suma en la pregunta al 2N lnN en el título requiere demasiados cálculos para explicar en detalle aquí, pero se basa en el entendimiento de que el costo para clasificar una matriz de N elements ( C(N) ) se pueden expresar en términos de ordenación de una matriz de N-1 elements ( C(N-1) ) y un factor que es directamente proporcional a N .

respondido por el Bart van Ingen Schenau 06.08.2013 - 14:52
2
  1. Parece que N + 1 como el número de comparaciones para el paso de partición es un error en el libro. Debe averiguar para cada uno de los elementos no pivotes N – 1 si es menor o mayor que el pivote, lo que requiere una comparación; por lo tanto, N – 1 comparaciones en total, no N + 1. (Considere el caso más simple, N = 2, es decir, un pivote y otro elemento: no hay espacio para hacer tres comparaciones entre dos elementos).

  2. Considere el caso donde el pivote elegido es el elemento más pequeño (k = 1). Esto significa que la matriz se divide en una parte vacía a la izquierda (no hay elementos que sean menores que el pivote) y una parte a la derecha que contiene todos los elementos excepto el pivote (todos los demás elementos son mayores que el pivote). ). Esto significa que los subproblemas que ahora desea resolver recursivamente tienen tamaños 0 y N – 1 (k – 1 y N – k), respectivamente, y requieren comparaciones de C (0) y C (N – 1); por lo tanto, C (0) + C (N – 1) en total.

    Si el pivote es el segundo elemento más pequeño (k = 2), los tamaños de los subproblemas son 1 y N – 2 (k – 1 y N – k; un elemento a la izquierda, porque es el único uno más pequeño que el pivote). Por lo tanto, la resolución recursiva de estos subproblemas requiere comparaciones con C (1) + C (N – 2). Y así sucesivamente si el pivote es el tercer elemento más pequeño, el cuarto, etc. Estas son las expresiones en los numeradores.

    Debido a que el pivote se elige al azar de entre los N elementos, cada caso (el pivote es el más pequeño, el segundo es el más pequeño, etc.) ocurre con la misma probabilidad 1 / N. De ahí viene la N en los denominadores.

respondido por el chirlu 06.08.2013 - 10:44

Lea otras preguntas en las etiquetas