buzhidao 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

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

I have the programmed the following code,
ought to be O(n) but actually it runs really slow.
is the normal recursion and it is O(n^2) solution, but actually it runs much faster than
. 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 Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download