algorithm - 将 Big-O 递归算法简化为线性

Question

我遇到了以下问题:

F(n)= 0 when n = 0;
F(n)= 1 when n = 1;
F(n)= F(n-1) + F(n-2) when n>1;

我已经可以像这样递归地解决这个问题了:

int F(int n) {
    if(n=0) return 0;
    if(n=1) return 1;
    if(n>1) return F(n-1) + F(n-2);
}

但是复杂度是O(n^2)。如何解决复杂度为 O(n) 的问题？

我需要读什么书才能解决这样的问题？

Answer 1

这个函数正是您要找的。是的，这就是动态规划。

static ArrayList<Double> getSeries(int n)
{
    ArrayList<Double> series = new ArrayList<>();
    series.add(0.0); // This is working as replacement of the F(0)
    series.add(1.0); // This is working as replacement of the F(1)
    double x, y;

    for (int i = 1; i < n; i++)
    {
        x= series.get(i - 1); // This is working as replacement of the F(n-2)
        y = series.get(i); // This is working as replacement of the F(n-1)
        series.add(x + y);
    }

    return series;
}

在这里试试这个代码:- https://ideone.com/IMixm9

此处可以看到计算空间和时间的基本权衡。

之前

Space Complexity :- log 
Time Complexity  :- 2^n

现在

Space Complexity :- n
Time Complexity  :- n