Сколько дополнительных вызовов функций требуется fib (n), если "LINE 3" удален?

Question

Я только что получил этот вопрос на собеседовании и не знал, как рассчитать ответ.
Сколько дополнительных вызовов функций требуется fib (n), если "LINE 3" удален? Ответ должен быть в терминах по п.

int fib(int n) {
  if(n == 0) return 0;
  if(n == 1) return 1;
  if(n == 2) return 1; //LINE 3 HERE <---

  return fib(n - 1) + fib(n - 2);
}

Answer 1

Это может быть легко рассчитано. Старый код:

TO(0)=TO(1)=TO(2)=1
TO(n)=TO(n-1)+TO(n+2)+1

Новый код:

TN(0)=TN(1)=1
TN(n)=TN(n-1)+TN(n-2)+1

Разница вычисляется просто путем вычитания этих двух:

D(0)=D(1)=0
D(2)=3-1=2
D(n)=TN(n)-TO(n)=TN(n-1)+TN(n-2)+1-(TO(n-1)+TO(n+2)+1)
    =(TN(n-1)-TO(n-1))+(TN(n-2)-TN(n-2))+(1-1)
    =D(n-1)+D(n-2)

Что означает, что разница представляет собой последовательность Фибоначчи, начинающуюся с 0,0,2. Для него также можно рассчитать выражение закрытой формы.

Answer 2

Требуемое количество дополнительных вызовов , также Фибоначчи вид последовательности.

0 0 2 2 4 6 10 16 26 42 68 110 178 288 466

#include<iostream>
using namespace std;

int a = 0;
int b = 0;

int fib(int n) {
    a++;
  if(n == 0) return 0;
  if(n == 1) return 1;
  if(n == 2) return 1; //LINE 3 HERE <---

  return fib(n - 1) + fib(n - 2);
} 

int fib1(int n) {
    b++;
  if(n == 0) return 0;
  if(n == 1) return 1;

  return fib1(n - 1) + fib1(n - 2);
}

int main(int argc, char* argv[])
{
    for(int i =0 ;i<15;i++)
    {
        fib(i);
        fib1(i);

        cout<<b-a<<" ";

        b = a = 0;
    }
}

ПРИМЕЧАНИЕ: я думал, что это будет некоторая константа, но ...

Answer 3

Предположим, что 3-й строки нет, и вычислим f (3):

f(3) = f(2) + f(1)
f(1) = 1
f(2) = f(1) + f(0)
f(0) = 0
f(1) = 1

Требуется 3 вызова, чтобы вычислить f (2) сейчас. Если была третья линия, то это будет сделано за 1 звонок.

Сложность этого алгоритма (без 3-й строки) составляет O(2^n). Когда вы добавляете строку 3, которая содержит явное решение для случая, когда n = 2, сложность становится O(2^(n-1)), что равно (1/2) * O(2^n) = kO(2^n), где koefficient k = 0,5. Если вы добавите явное решение для случая, когда n = 3, тогда вы получите k = 0,25 и так далее. Когда вы добавите p явные решения, сложность будет:

    1
O (--- * 2^n)
   2^p 

Это означает, что если вы вычислите ответ для n от 1 до n и сохраните все вычисленные решения, то вы получите p = n - 1 и алгоритм для каждого из n шагов, а сложность будет 2*O(n).