0

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

例如,如果我有递归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-> 无穷大时,表达式变为零

这不是说我的猜测太高了吗?但是,我知道事实并非如此。谁能看到我到底在哪里扼杀这个理论?谢谢。

4

2 回答 2

2

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)

于 2010-09-19T14:53:21.010 回答
2

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

你是对的n --> infinity,那么1/(2^(n-2)) --> 0。但是,这并不意味着c --> 0,表明您的猜测太高了。相反,这表明c >= 0. 因此,c可以是任何正常数,这意味着您的猜测很严格。

于 2015-10-05T01:03:08.623 回答