朗道符号

Question

海兰

如何显示以下内容： F（N）= < F（N-1）+ F（N-2）+ ... + F（1）意味着F（N） = O（2^N）

我认为，我们可以假设，f为单调递增=>

F（N）< = N * F（N-1）

Answer 1

你是在正确的轨道上

F（1）= < f（0）
f（2）< = f（0）+ f（1）

| f（2）| < = f（0）| 2^2 |
| f（1）| < = f（0）| 2^1 |
| f（0）| < = f（0）| 2^0 |
其中f（0）是一个常数

令x是一个常数（等于f（0））

假设| F（I）| < = x | 2^i |对于所有的值i < = n
然后f（n + 1）< = f（n）+（f（n-1）+ f（n-2）+ ... + f（0））
==> | f（n + 1）| < = | f（n）| + |（f（n-1）+ f（n-2）+ ... + f（0））|
==> | f（n + 1）| < = x | 2^n | + x | 2^n-1 | + x | 2^n-2 | + .. + x
==> | f（n + 1）| < = x | 2 ^（n + 1）|
所以情况下n表示情况下，n + 1

而且通过感应将权利要求适用于在N-

所有N和从大O符号的定义中，f（x）是在O（2^N ）

Answer 2

也许通过感应：F （j）< = c * 2 ^（j）对于所有j < n

然后f（n）< = c（2 ^（n-2）+ 2 ^（n-3）+ ... + 2 ^（1））< = c * 2 ^（n + 1）

我不确定c是否依赖j，所以我们是否应该写： 然后f（n）< = c_（n-2）（2 ^（n-2）+ c_（n-3） 2 ^（N-3）+ ... + C_1 2 ^（1））< = C * 2 ^（N + 1）