buzhidao buzhidao - 1 month ago 8
C++ Question

Why my dynamical programming of fibonacci doesn't give a linear time?

I am watching this video. Basically it says that using a

dictionary
(python's language?) will make calculate fibonacci from time O(n^2) to O(n).

I have the programmed the following code,
fibo1
ought to be O(n) but actually it runs really slow.
fibo2
is the normal recursion and it is O(n^2) solution, but actually it runs much faster than
fibo1
. How can I understand this?

#include <iostream>
#include <map>
int fibo1(int i, std::map<int,int>& m);
int fibo2(int i);

int main()
{
std::map<int,int> m;
m[1] = 1; m[2] = 1;
int n = 40;
std::cout << fibo1(n,m);
//std::cout << fibo2(n);
return 0;
}

int fibo1(int i, std::map<int,int>& m) {
if(m[i]==0) {
return fibo1(i-1,m)+fibo1(i-2,m);
}
return m[i];
}

int fibo2(int i) {
if(i==1 || i==2) {
return 1;
}

return fibo2(i-1)+fibo2(i-2);
}

Answer

You never actually write the fib[n] at m[n], so you never look up anything and always recalculate it. Use m[i] = fibo1(i-1,m) + fibo1(i-2,m); in the if statement rather than the return line.