※ 引述《SiriusJinn (假斯汀)》之銘言：
: wiki裡有一段不太懂意思
: http://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7
: ==============================================================================
: 大O符號在分析演算法效率的時候非常有用。舉個例子，解決一個規模為 n 的問題所花費
: 的時間（或者所需步驟的數目）可以被求得：T(n) = 4n2 - 2n + 2。
: 當 n 增大時，n2 項將開始占主導地位，而其他各項可以被忽略——舉例說明：當 n =
: 500，4n2 項是 2n 項的1000倍大，因此在大多數場合下，省略後者對錶達式的值的影響
: 將是可以忽略不計的。
: 進一步看，如果我們與任一其他級的表達式比較，n2 項的係數也是無關緊要的。例如一
: 個包含 n3 或 2n 項的表達式，即使 T(n) = 1,000,000n2 ，假定 U(n) = n3 ，一旦
: n 增長到大於1,000,000，後者就會一直超越前者(T(1,000,000) = 1,000,0003 =
: U(1,000,000))。
: ==============================================================================
: 有人可以幫忙白話一點說明嗎？
: 謝謝！
我試試看:)
我們回過頭來看 Big-O Notation 的定義，
假設 f(x)、g(x) 是兩個已知函數，
那麼我們稱「在 x 趨近於無限大時，f(x) = O(g(x))，若且唯若存在正實數 M, x[0]，
使得對所有 x>x[0] 皆滿足 |f(x)| ≦ M|g(x)|」
注意上式 f(x) = O(g(x)) 中的等號，
是單向性的，我們不可以寫 O(g(x)) = f(x)。
回過頭來，
看看上面那段鬼話，
第一段他要說的是，
「為什麼這個多項式 T(n) = 4n^2 - 2n + 2 可以寫成 O(n^2)」
我們從定義開始說明~
對所有 n＞n[0]＝1
|4n^2 - 2n + 2|≦4n^2 + 2n + 2
|4n^2 - 2n + 2|≦4n^2 + 2n^2 + 2n^2
|4n^2 - 2n + 2|≦8n^2
|4n^2 - 2n + 2|≦8|n^2|
→ T(n) = O(n^2) （這裡取 M = 8, x[0] = 1）
從這個例子中，
很清楚的說明了為什麼:)
而第二段要說的是，
「為什麼 T(n) = 1,000,000n^2 成長的比 U(n) = n^3 ，即使 T(n) 的係數是這麼大」
我想這應該是很好說明的~
只要 U(n) 的領導項次數比 T(n) 高，
那我們總能找到一個夠大的 n ，使得 U(n)>T(n) ，是吧？
事實上同樣的道理還可以比較 O(2^n) 和 O(n!)，
哪個成長比較快呢？O(n!)
EDIT:
我想版主看到的應該是關於誤差用的 O() ，
請看這個條目^^
Big O Notation - Infinitesimal asymptotics
http://en.wikipedia.org/wiki/Big_O_notation#Infinitesimal_asymptotics
如果有不正確的地方，
歡迎指正^^
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.224.172.20
※ 編輯: gba356 來自: 61.224.172.20 (12/03 21:29)