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

Question

我可以清楚地看到 N^2 以 c2^N 为界，但是我如何通过使用 big-O 的正式定义来证明它。我可以简单地用 MI 来证明

这是我的尝试.. 根据定义，对于任何 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

score 8 · Accepted Answer

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

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

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

x ² < 2 ^x对于所有x > 2

此时您可以记录双方（因为如果 log( x ) > log( y )，则x > y。）假设您使用的是 base-2 日志，您会得到以下信息

日志(x ² ) < 日志(2 ^x )

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

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都成立。

score 1 · Accepted Answer

1

于 2021-06-07T12:37:35.880 回答

score 0 · Accepted Answer

为了改进接受的答案：

你必须证明 x^2 < 2^x 对于所有 x > 2

两边取log，我们必须证明： 2·log(x) < x for all x > 2

因此我们必须证明函数 h(x)=x-2·log(x)>0 对于所有 x>2

h(2)=0

对 h(x) 对 x 微分，我们得到 h'(x)= 1 - 1/(x·ln(2))

对于所有 x>2，h'(x) 总是大于 0，因此 h(x) 不断增加，并且由于 h(2)=0，因此证明对于所有 x > 2，h(x) > 0，或 x^2 < 2^x 对于所有 x > 2

3 回答 3