我正在尝试对算法复杂性进行一些猜测,但是每次我尝试使用指数时间进行猜测时,我的猜测/验证方法似乎都失败了。我确定我做错了什么荒谬的事情,我自己找不到。
例如,如果我有递归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-> 无穷大时,表达式变为零
这不是说我的猜测太高了吗?但是,我知道事实并非如此。谁能看到我到底在哪里扼杀这个理论?谢谢。