Deje que una función llamada QUARTERSORT que obtiene una matriz y la ordene de la siguiente manera:

  • Si n <100`, usa el QUICKSORT normal
  • De lo contrario, dividimos la matriz en A1 = A[1,...,n/4] y A2 = A[(n/4)+1,...,n].
  • Luego, llamamos QUARTERSORT dos veces: B1 = QUARTERSORT(A1) y B2 = QUARTERSORT(A2).
  • Finalmente, fusionamos B1 y B2.

Ahora, ¿por qué la recurrencia es T(n) = T(0.25n) + T(0.75n) + O(n) y no T(n) = T(0.25n) + T(0.75n) + O(nlogn)?

0
AlonAlon 16 feb. 2015 a las 19:13

3 respuestas

La mejor respuesta

Intuitivamente, puede ignorar la parte sobre ordenación rápida, porque solo ocurre con n pequeño, y la notación con O grande solo habla de valores de n que son "suficientemente grandes". Entonces las partes del algoritmo son:

  1. Invocación recursiva en 1/4 de la entrada: T(1/4 * n)
  2. Invocación recursiva en 3/4 de la entrada: T(3/4 * n)
  3. Fusionando: O(n)

Un poco más formalmente: la complejidad temporal de la ordenación rápida es O(1). Esta adición se puede ignorar con seguridad, porque hay partes más grandes en la complejidad del tiempo, como O(n).

1
anatolyg 16 feb. 2015 a las 16:21

Quick Sort necesita O(n) para encontrar el pivote. Una vez que se encuentra el pivote, permanece sin cambios.

El tamaño de 2 subproblemas es O (N / 4) y O (3N / 4), por lo que la recurrencia es

T(n) = T(0.25n) + T(0.75n) + O(n)

1
zs2020 16 feb. 2015 a las 16:25

La recurrencia es T(n) = T(0.25n) + T(0.75n) + O(n), porque cada paso del algoritmo por sí solo es O(n). Dividir la matriz en 2 partes es O(n), y fusionar las dos partes es O(n), por lo que cada paso por sí solo es O(n), lo que nos da un total de T(n) = T(0.25n) + T(0.75n) + O(n) como se esperaba. .

1
amit 16 feb. 2015 a las 16:18