Как решить рекуррентное соотношение для этого алгоритма умножения

Question

Как установить верхнюю границу big-O для числа раз, которое функция вызывает себя, как функцию b для следующего:

  function multiply(a,b)
     if b = 0 then return 0
     else if b is even then
       t := multiply(a, b/2);
       return t+t;
     else if b is odd then
       t := multiply(a, b-1);
       return a+t;

это функция для умножения двух целых чисел,Я запутался в том, как обрабатывать условия if if для отношения повторения.Я думал, что ответом является T (n) = T (n / 2) + T (n-1).Это правильно?

Answer 1

 function multiply(a,b)
     if b = 0 then return 0
     else if b is even then
       t := multiply(a, b/2);
       return t+t;
     else if b is odd then
       t := multiply(a, b-1);
       return a+t;

Следовательно:

F(0) = 0
If Even: F(N) = F(N/2) + 1 
If Odd-Even: F(N) = F(N-1) + 1 = F((N-1)/2) + 2 <-next number is definitely even

Решение случая нечетного-четного-нечетного-четного (худший сценарий):

F(N) = F((N-1)/2) + 2 = O(LogN)

Еще один способ решения проблемчто мы знаем, что случай нечетно-четно-нечетно-четный имеет максимальную вдвое глубину случая четно-четно-четно-четного.Четный единственный случай имеет глубину LogN, таким образом, случай нечетный-четный-нечетный-четный имеет не более 2*LogN глубина.

Answer 2

Оцените следующие две точки:

• Вызов multiply со входом нечетный вызовет вызов на тот же вход минус один, который является четным числом.Для получения четного номера потребуется еще один вызов.
• Вызов multiply с четным входом вызовет другой вызов с уменьшенным вдвое входом.Полученное число будет либо четным, либо нечетным qv вышеупомянутой точки.

В худшем случае, начиная с четного ввода, потребуется два вызова для деления пополамввод передается в multiply.Это поведение согласуется со временем выполнения 2*O(lgN) (где lg - база журнала 2).Это то же самое, что и O(lgN).