大 O.

Big O 表示法為函式的增長提供了上限。直觀的 f ∊ O(g)，f 增長最多快 g。

正式 f ∊ O(g) 當且僅當有一個正數 C 和一個正數``n 這樣對於所有正數 m > n 我們有

C⋅g(m)> f(m)。

直覺這個定義

關於 C 的直覺

C 負責吞嚥功能中的常數因素。如果 h 是 f 的兩倍，我們仍然有 h ∊ O(g)，因為 C 可以是兩倍大。為此，有兩個基本原理：

• 更簡單的符號：f ∊ O(n) 優於 f ∊ O(7.39 n)。
• 抽象：在這些考慮中吞下任何時間單位，因為它們沒有任何好處; 它們在機器之間有所不同，演算法可以免費評估。由於 C 吞噬了恆定因子，因此複雜性等級甚至在機器上保持相同的十倍速度。

關於 n 的直覺

n 負責吞嚥初始湍流。一種演算法可能具有初始化開銷，這對於小輸入來說是巨大的，但從長遠來看會得到回報。n 的選擇允許足夠大的輸入來獲得焦點，而忽略初始拉伸。

關於 m 的直覺

m 的範圍超過所有大於 n 的值 - 以形成“從 n 開始，這就成立”的想法。