作者SiriusJinn (假斯汀)
看板Math
標題Re: [分析] 數值分析裡的誤差O？
時間Wed Dec 3 12:50:32 2008
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))。
==============================================================================
有人可以幫忙白話一點說明嗎？
謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.120.32.174
推 CombatSniper:通常來說O表達其最大次方項 12/03 13:37
→ CombatSniper:例如T(n)=4n^2-2n+2 O(n)=n^2 12/03 13:37
→ CombatSniper:主要指出會造成其時間上升的最主要項 12/03 13:38
→ CombatSniper:有些時候可能是指數 對數 甚至於其他都可能 12/03 13:38
→ CombatSniper:O(n)是以多項式花費最小 指數花費時間最大 12/03 13:38
→ CombatSniper:一個問題如果找不出任何多項式時間的解法 便被稱為 12/03 13:39
推 CombatSniper:NP-hard 12/03 13:41
推 xcycl:NP-hard 不是這樣吧 _A_ ... 12/03 17:51