 buzhidao - 3 years ago 108
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; m = 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);
}
`````` person
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.