朗道符號

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）