Usando divide y vencerás para s = (a ^ n), a> 0 y (n = 2 ^ k) a) muestra que el número de multiplicación usando recurrencia M (n) = M (n / 2) +1 para n> 1 y M (1) = 0 es?

Answer 1

OK, primero escribamos el pseudocódigo:

procedimiento POWER (a, n)
si (n = 1)
devolver un
si (n% 2 = 0)
retorno (POTENCIA (a, n / 2)) ^ 2
más
hacha de retorno (POTENCIA (a, (n – 1) / 2)) ^ 2

Como vería usando divide-and-conquer, en cada paso, divide el problema en dos subproblemas idénticos de tamaño [math] \ lfloor n / 2 \ rfloor [/ math]. Los otros pasos tardan un tiempo constante en completarse. Esto es cierto para todos [matemáticas] n> 1 [/ matemáticas]. Para [matemática] n = 1 [/ matemática], el algoritmo toma tiempo constante. Por lo tanto, la relación de recurrencia correcta aquí debería ser

[matemática] M (n) = M (\ lfloor n / 2 \ rfloor) + O (1) [/ math]

[matemáticas] M (1) = O (1) [/ matemáticas]

Del mismo modo para el otro problema.

Actualización: Parece que OP también quiere resolver la recurrencia. La forma más intuitiva de hacer esto es ver esto como un árbol de recurrencia (o, en el presente caso, una cadena de recurrencia). Por ejemplo, para [matemáticas] n = 8 [/ matemáticas], su árbol de recurrencia se ve a continuación:

Por lo tanto, para [math] 2 ^ {k – 1} \ leq n <2 ^ k [/ math], habrá exactamente [math] k [/ math] nodos en el árbol de recurrencia, cada uno de los cuales toma un (casi ) tiempo constante para resolver. Por lo tanto, [math] k = \ lfloor \ log_2 {n} \ rfloor [/ math]. Por lo tanto, el límite en su algoritmo es [matemática] O \ left (\ log_2 {n} \ right) [/ math].

También es posible que desee ver el teorema del Maestro, que es bastante útil para resolver las recurrencias.