algorithm - 如何将递归定义的输入大小函数转换为问题输入大小的直接函数？

Question

假设我有一个对大小为 n 的输入进行运算的算法，并且我知道 n 所花费的时间是 n-1 所花费时间的两倍。我可以观察到在这个简单的情况下(假设 n = 0 需要 1 秒)算法需要 2ⁿ 秒。

是否有一种通用方法可以将递归定义的定义转换为更熟悉的直接表达式类型？

Answer 1

Master Theorem

特别是:

有 T(n) = aT(n/b) + n^c

如果 log_ba < c，则 T(n) = O(n^c)

如果 log_ba = c，则 T(n) = O(n^clog[n])

如果log_ba > c，则T(n) = O(n^log_ba)

这是一个需要知道的有用定理，但不能完全回答您的问题。

您正在寻找的是递归关系的生成函数。一般来说，这些只能解决非常简单的情况，即当 f(n) = Af(n-1) + Bf(n-1) 和 f(0) = f(1) = 1(或 f(1) =一个)。其他递归关系很难求解。

参见 linear recurrence relation了解更多信息。