big-o - 用 big-O 证明 N^2 是 O(2^N)

Question

我可以清楚地看到 N^2 受 c2^N 的限制，但是我如何使用 big-O 的正式定义来证明它。我可以简单地通过 M.I. 证明这一点。

这是我的尝试..
根据定义，对于任何 n>n0，都存在一个常数 C，它
f(n) <= Cg(n)
在哪里
f(n) = n^2
和
g(n) = 2^n

我应该把日志带到两边并解决C吗？

还有一个关于斐波那契数列的问题，我想解决递推关系。

int fib(int n){
   if(n<=1) return n;
   else return fib(n-1) + fib(n-2);

等式是..

T(n) = T(n-1)+T(n-2)+C // where c is for the adding operation

所以

T(n) = T(n-2) + 2T(n-3) + T(n-4) + 3c 

还有一个

T(n) = T(n-3) + 3T(n-4) + 3T(n-5) + T(n-6) + 6c

然后我开始迷失以形成一般方程 i
图案有点像帕斯卡三角形？

 t(n) = t(n-i) + aT(n-i-1) + bT(n-i-2) + ... + kT(n-i-i) + C 

Answer 1

正如您所指出的，要查看 f(x) ϵ O(g(x)) 是否需要找到...

...一些 c > 0 和

...一些x0

使得 f(x) < c·g(x) 对于所有 x > x0。

在这种情况下，您可以选择 c = 1 和 x0 = 2。您需要证明的是

x2 < 2x 对于所有 x > 2

此时，您可以记录双方(因为如果 log(x) > log(y)，则 x > y。)假设您正在使用 base-2 log，您会得到以下结果

日志(x2) < 日志(2x)

根据对数的标准定律，你得到

2·log(x) < x·log(2)

由于 log(2) = 1 这可以写成

2·log(x) < x

如果我们设置 x = 2，我们得到

2·log(2) = 2

由于 x 的增长速度比 log(x) 快，我们知道 2·log(x) < x 对所有 x > 2 成立。