这种递归关系代表哪种算法？

Question

看一下算法复杂度的递归关系：

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

这个递归关系代表什么样的算法。注意，这里有一个minus而不是plus，所以它不能是一个分而治之的算法。

作为递归关系，什么样的算法会有这样的复杂性？

Answer 1

基于给定的时间复杂度，它是一个指数算法。

要将大小减少1，您需要将时间乘以2(大约)

因此，它不属于任何多项式时间算法范式，如分而治之，动态规划，...

Answer 2

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)：存在正常量c和n0，使得0 <= f(n) <= c g(n)适用于所有n >= n0 }

因此，为了消除-1的影响，我们只需要将隐藏常量c增加1。

所以，只要你的基本情况像O(1)，O(n)和n > 0一样复杂，你就不应该关心-1。换句话说，如果你的基本情况使得n中的递归T(n) = 2 T(n-1)至少是指数级的，那么你就不关心这个-1了。

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