Encontrar relaciones de recurrencia de un algoritmo

Question

Estoy leyendo mi libro de texto algoritmos, y estoy leyendo acerca de las relaciones de recurrencia y la búsqueda de los algoritmos de gran complejidad O. Me encuentro con esta línea

"In the case of the merge-sort algorithm, we get the recurrence equation:

    t(n) = b                  if n < 2

         = 2t(n/2) +bn        if n >= 2

for b > 0

mi respuesta fue "¿cómo diablos lo que sabemos que?!?!"

Así que me pregunto si hay un enfoque sistemático, o simplemente una forma lógica de conseguir que estas relaciones de recurrencia de los algoritmos

puede explicar alguien donde el B y los dos de 2 vienen?

Answer 1

El algoritmo de ordenamiento por mezcla se puede resumir como:

mergesort (array A) {
   mergesort (first half of A);
   mergesort (second half of A);
   merge the two halves and return;
}

Hay una (N) algoritmo O a la fusión de dos matrices de longitud N, es decir, su complejidad es bN para alguna constante b > 0.

Suponiendo que la complejidad de mergesort es T (N). Desde la mitad de N es N / 2, vemos que:

mergesort (array A) {                    T(N)    =
   mergesort (first half of A);          T(N/2)  +
   mergesort (second half of A);         T(N/2)  +
   merge the two halves and return;       bN
}

lo que explica la N = 2 caso.

El N <2 caso (el caso base, donde se detiene la recursión) es trivial.

Answer 2

Bueno, esta afirmación es (presumiblemente) la conclusión de una discusión, o al menos una declaración, el algoritmo en cuestión. Sin los detalles que sólo se pueden hacer conjeturas, que sería algo así:

• lo primero que hace es el algoritmo de verificación si se le pide para procesar 0 o 1 elementos. Si eso es cierto, se devuelve inmediatamente. Por lo tanto, a continuación, n < 2, hay un costo fijo - llamarlo b
• Para n >= 2, el algoritmo divide su entrada en dos piezas, cada una de tamaño n/2, e invoca sí mismo en cada pieza. Cada uno de tales invocación tendrá un coste de t(n/2), y hay dos de estas invocaciones
• Hay, pues, un coste adicional para fusionar las dos piezas juntas - este costo será proporcional al n - lo llaman b veces n

La única pequeña rareza es que no es del todo evidente por qué los dos factores constantes que se presentan deben ser los mismos -. Sino que forma parte del eje de análisis de orden O es que los factores constantes con el tiempo no importan

Answer 3

T(n) = c if n < d
     = A*T(n/b) + f(n)

donde d> = 1 y hay unos subproblemas y los subproblemas son en la mayoría de tamaño n / b. f (n) es el tiempo adicional total que se necesita para dividir el problema en subproblemas y combinar las soluciones subproblema en una solución a todo el problema.

esto es para dividir y conquistar algoritmos.

Me pregunto por qué hay 2 subproblemas en combinación especie?