指數函數的大O符號

我注意到1000n或10n的大O與O（n）是相同的，但是2^n和3^n的大O是不同的：O（2^n ）和O（3^n），我沒有得到的是爲什麼我們不能忽略這種情況下的常量（2或3）以及是否有任何數學證明證明這一點？指數函數的大O符號

來源

2013-09-29 fYre

您不會忽略大O符號中的常量。你忽略係數。 2和3是基礎，而不是係數。 – kqr

你能說出Big-Oh的定義嗎？記住Big-Oh有一個數學定義，不應該直接使用。記住「有時你可以忽略常量」是一種壞習慣，在我看來。 – rliu

因爲k的常數值滿足不等式3^n <= k * 2^n的任意大n。因此f(n) = 3^n不是O(2^n)的成員。

請參閱http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations。

來源

2013-09-29 18:30:23

準確地說，您正在展示一個聲稱「O（3^n）= O（2^n）」的反例。特別是，'f（n）= 3^n'在'O（3^n）'中，但不在'O（2^n）'中，使用上面給出的參數。因此，這些集合不等於通過擴張性公理 – rliu

@roliu：我不知道這個公理是什麼，但是，這是暗示的論證;） –

這是最流行的集合論中的一個公理，ZFC：https：/ /en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory。它只是說「如果它們包含相同的元素，則兩組相等」。從來沒有人以真實的證據引用它，但我只是試圖說服SO開始使用實際的數學推理而不是直覺（對於數學術語來說，這是非常冗長的）。如果您只是想在編寫代碼時決定使用哪個實現，則可以使用直覺。當有人說「證明這一點」時，我認爲你應該，你知道，使用數學:) – rliu

雖然對於原來的提問者來說這可能不再有用，
我認爲可以以更簡單的方式接近它。

O形表示法的基本defenition：當且僅當F（G）將是O（G（N）），
則存在一個有理數C，對於其保持使f（G）= C * G（N），對於n> = N0
（N0爲一個數字，你要振作精神）

讓我們嘗試應用此3爲O^N（2^n）的
3^N = 2^n * c
3^n = 2^n *（3^n/2^n）
3^N = 2^N *（3/2）^ n的
3^N = 2^N * 1.5^N

這意味着C = 1.5^n的是不是一個合理的數字，但它本身就是一個指數函數。

在另一方面，以下爲O 3^N（2^n）的相同，我們將得到2^N < = 3^N *（2/3）^ n的

這可能看起來像是一個衝突，直到你意識到所有n> 0的0.75^n < 1，這意味着如果你採取任何c> 1，它將大於0。從n = 0開始的67^n

來源

2014-10-17 11:56:05

爲了應對兩個複雜性f（n）和g（n）你應用的極限： lim_ {n - > \ inf} f（n）/ g（n）和你有三個可能的答案：

1）lim_ {n - > \ inf} f（n）/ g（n）= 0;這意味着f（n）∈O（g（n））和g（n）∉O（f（n））

2）lim_ {n-> \ inf} f（n）/ g n）= +/- inf;這意味着f（n）∉O（g（n））和g（n）∈O（f（n））

3）lim_ {n-> \ inf} f（n）/ g n）∈實數;這意味着f（n）∈O（g（n））和g（n）∈O（f（n））

然後去demostrade 2^n∈O（3^n）

lim_ {N - > \ INF} 2^N/3^N = lim_ {N - > \ INF}（2/3）^ n = 0的

和IS實例闡述，並且我們也demostraded 3 （2^n），並且很容易看出，這使得極限收斂到0，那麼極限的結果取決於常數，我的意思是lim_ {n-> inf} a^n = 0如果0 < a < 1並且lim_ {n-inf} a^n = inf如果a> 1;

爲了更好地理解檢查：算法導論，第三版通過托馬斯·H·科門，查爾斯·E·萊澤森，羅納德L.維斯特和克利福德·斯坦

我的算法教授，我希望它幫助您。保重。

來源

2017-02-08 17:31:31

指數函數的大O符號

回答

相關問題