使用猜测/验证方法查找算法的下界

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)。

Answer 2

我认为Itay输入后你的代数是正确的，但你对c >= 1/(2^(n-2))的理解是错误的。

你是对的，因为 n -->无穷大，然后1/(2^(n-2)) --> 0 。然而，这并不意味着c --> 0，表明你的猜测太大了。相反，这表明c >= 0。因此，c 可以是任何正常数，这意味着您的猜测是严格的。