用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

然后我开始迷失形成一般方程式我的模式有点像帕斯卡三角形？

 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和
• ......有些x ₀

这样,对于所有x> x ₀,f(x)<c·g(x).

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

    所有x> 2的x ² <2 ^x

此时你可以记录两面(因为如果log(x)> log(y),那么x> y.)假设你使用的是base-2 log,你得到以下内容

    log(x ²)<log(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.