Сколько дополнительных вызовов функции действительно выдумывает (n), требуют, если “СТРОКА 3” удалена?
Я просто получил этот вопрос на интервью и понятия не имел, как вычислить ответ.
Сколько дополнительных вызовов функции действительно выдумывает (n), требуют, если "СТРОКА 3" удалена? Ответ должен быть в терминах на n.
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);
}
3 ответа
Его можно легко вычислить. Старый код:
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. Для нее также можно вычислить выражение в закрытой форме.
Требуется количество дополнительных вызовов , а также последовательность типа Фибоначчи .
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;
}
}
ПРИМЕЧАНИЕ: Я думал, что это будет некоторая константа, но ...
Предположим, что нет третьей строки, и вычислим f (3):
f(3) = f(2) + f(1)
f(1) = 1
f(2) = f(1) + f(0)
f(0) = 0
f(1) = 1
Теперь для вычисления f (2) требуется 3 вызова. Если была 3-я строка, то это будет сделано за 1 вызов.
Сложность этого алгоритма (без 3-й строки) составляет O (2 ^ n) . Когда вы добавляете строку 3, которая содержит явное решение для случая, когда n = 2 , сложность становится O (2 ^ (n-1)) , что равно ( 1/2) * O (2 ^ n) = kO (2 ^ n) , где коэффициент 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) .