---

---

※ 引述《hank001.bbs@fpg.m4.ntu.edu.tw (hank001)》之銘言：
: as title
: 小弟是初學者(我是自己在看書，資料結構)
: 看到什麼O(n^2)
:  這是怎麼出來的啊？
: 可以告訴我嗎？
: 問題很笨還望高手不吝指教
: 或是有什麼網站有在教的嗎？

O() 的嚴格定義，其實是一個函數的集合。
g(x) = O(f(x)) 表示的是說

         f(x)
  lim   ------  < inf
 x->inf  g(x)

inf 表示無限大。

所以，說一個演算法的複雜度是 O(n^2)，表示它需要大約或小於 n^2 個動作。常數
項不計。例如，3n^2 還是 O(n^2)。
使用這樣的記號，是因為很多演算法，在執行時所需要的時間，往往是十分複雜的。
例如，一個排序演算法在最糟的情形下，需要的動作次數可能是 2n^2 + 3n - 5 之類
的麻煩式子。所以，用 O() 記號，就可以直接寫成 O(n^2)。

--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: hfc230-155.hc.ethome.net.tw

--
Shaken, Not Stirred.
--
※ 作者: TL 時間: 2013-01-27 18:45:22