algorithm - 这个递归关系代表了什么样的算法？

Question

<分区>

Answer 1

T(n) =  2 T(n-1)-1
T(n) =  4 T(n-2)-3
T(n) =  8 T(n-3)-7
T(n) = 16 T(n-4)-15
...
T(n) = 2^k T(n-k) - 2^(k-1)

如果，例如T(1) = O(1)然后

T(n) = 2^(n-1) O(1) - 2^(n-2) = O(2^(n-1)) = O(2^n)

呈指数级增长。

---

现在让我们看看O(1) - 1 = O(1) .来自 CLRS:

O(g(n)) = { f(n) : there exist positive constants c and n0 such that 0 <= f(n) <= c g(n) for all n >= n0 }

从而消除 -1 的影响我们只需要增加隐藏常量 c一个。

因此，只要您的基本案例具有像 O(1) 这样的复杂性, O(n)与 n > 0你不应该关心-1 .换句话说，如果你的基础案例重复发生 T(n) = 2 T(n-1)至少呈指数增长 n你不关心这个-1 .

---

示例:假设您被要求告知字符串是否为 S与 n characters 包含指定的字符。然后你像这样继续，你在 S[0..n-2] 上递归运行算法和 S[1..n-1] .当字符串是一个字符长度时，你停止递归，然后你只检查字符。