使用递归关系的算法时间复杂度

Question

我有两个关于使用递归关系分析时间复杂度的问题。

问题1.使用memoization时如何为算法建立递归关系？这可能吗？

例如，考虑计算斐波那契数列的第 n 项。该算法将是：

fib(n)
    if n < 2
        return n
    else
        return fib(n-1)+fib(n-2)

这段代码的递归关系是：

T(n) = T(n-1) + T(n-2) + c。这个的时间复杂度大概是2^n.

此代码的记忆版本为：

MemFib(n)
    if n < 2
        return n
    else
        if F[n] is undefined
            F[n] = MemFibo(n − 1) + MemFibo(n − 2)
        return F[n]

（注意：我从 Jeff Erickson 的笔记中提取了这个，可以在这里找到：http://jeffe.cs.illinois.edu/teaching/algorithms/。这个算法在第 5 章 - 动态规划中）

这个的复杂度是O(n)。我理解为什么这是 O(n) 因为我们将值存储在 table 'F' 中并尽可能执行查找但是我不知道如何在数学上证明这一点。

现在在我看来递推关系与第一个例子 (T(n-1)+T(n-2)+c) 相同，这显然是错误的。这个的递归关系怎么写？是否有可能为此编写一个关系，因为我们不会一直执行递归调用？如果不可能，你如何形式化地证明时间复杂度为 O(n)？

问题2.如何分析如下格式的算法的复杂度：

T(n) = aT(n/b) + cT(n/d) + x?

这里x是常数。

Answer 1

对于第一个问题，递归关系不再成立，因为 T(n) 可能有两个值，具体取决于它是否已经被调用 (O( n) 或 O(1)).

编写循环的一种方法是区分第一次和第二次调用：

Tf(n) = Tf(n-1) + Ts(n-2) + c = Tf(n-1) + O(1) + c = O(n).

对于第二题，可以扩展主定理：

在 x = O(1) 的具体示例中：

T(n) = θ(n^γ) with γ such as a*(1/b)^γ + c*(1/d)^γ = 1

Algorithm time complexity using recurrence relations