递归函数的时间复杂度，使用马斯特定理

Question

我需要使用马斯特定理找出图中函数的时间复杂度。 我认为函数是：T(n) = T(n-1) + c 但是用这个定理是不可能解决的。 请帮助我我试图解决它 3 小时大声笑，谢谢大家！

Answer 1

Master 定理适用于 T(n) = a*T(n/b) + f(n) 形式的递归，其中 a >= 1 和 b > 1 是常数。

您的递归是 T(n) = T(n-1) + c，其中 c >= 1 是常数。

n - 1 不能以 n / b 的形式使用 b 常数。所以在这里用马斯特定理是不可能的

但是可以很容易地通过归纳法证明你的递推给出了 T(n) = c * n 作为结果。

---

证明：

令 T(n) = c * n。你显然有 T(1) = T(0) + c = c * 0 + c = c ，这是基本情况。

假设它对给定的 n 有效，你有 T(n+1) = T(n) + c = c * n + c = c * (n+1)，所以它对 n + 1 也有效，通过归纳它对所有自然数 n 都有效。

Answer 2

令 b 等于基数，p 等于幂。 研究照片中的算法，递归应该是

T(n) = T(n-1) + O(log b^(p-1)) = T(n-1) + O(n)

由于f(n-1)占用的空间。看看你现在能不能使用 Master theorem