algorithm - 使用猜测/验证方法查找算法的下限

Question

我正在尝试对算法的复杂性进行一些猜测，但每次我尝试使用指数时间进行猜测时，我的猜测/验证方法似乎都失败了。我确信我做错了一些荒谬的错误，只是我自己找不到。

例如，如果我有循环 T(n) = 2T(n-1) + T(n-2) + 1 ，其中 T(1) = 0 和T(2) = 1。

通过迭代几次并插入值 n=3,4,5,6,7,8... 我们可以观察到对于 n>=8 的任何值，T(n) > 2^n , 因此 2^n 不是上限。

因此，根据这些信息，我尝试猜测 T(n)=O(2^n)

T(n) <= C(2^n)

2T(n-1)+T(n-2)+1 <= C(2^n)

2C(2^(n-1))+C(2^(n-2))+1 <= c(2^n)

C(2^n)-C(2^n+2^(n-2)) >= 1

C(-2^(n-2)) >= 1

C >= 1/(2^(n-2)) |当 n-> 无穷时，表达式变为零

这是不是说明我的猜测太高了？但是，我知道事实并非如此。任何人都可以看到我到底在哪里屠杀这个理论吗？谢谢。

Answer 1

从 2T(n-1)+T(n-2)+1 <= C(2^n) 的过渡至 2C(2^(n-1))+C(2^(n-2))+1 <= c(2^n)是错误的。
如果T(n) <= C(2^n)你可以推断出 2T(n-1)+T(n-2)+1 <= 2C(2^(n-1))+C(2^(n-2))+1但不是那个2C(2^(n-1))+C(2^(n-2))+1 <= c(2^n) .

请注意 2C(2^(n-1))=C(2^n)所以一定是2C(2^(n-1))+C(2^(n-2))+1 >= c(2^n) .