什麼是 Big-O 表示法

Big-O 表示法是用於談論功能的長期增長率的符號。它經常用於演算法分析，以討論演算法的執行時或空間複雜性等相關概念。

在常見用法中，使用 big-O 表示法來討論演算法的執行時如何按輸入的大小進行縮放。例如，我們假設選擇排序的執行時間為 O（n 2 ），因為執行時是作為要排序的陣列大小的函式的二次方增長。也就是說，如果你將輸入的大小加倍，則選擇排序的執行時間應該大約加倍。使用 big-O 表示法時，慣例是刪除係數並忽略低階項。例如，雖然技術上說二進位制搜尋在時間 O（2 log 2 n + 17）中執行並沒有錯，但它被認為是糟糕的風格，並且最好在時間 O（log n）中編寫二進位制搜尋執行。

形式上，big-O 表示法用於量化函式的長期行為。我們說 f(n)= O(g)（在某些來源中有時表示為 f(n)∈O（g(n)），如果有固定常數 c 和 n 0 ，則 f(n)≤c·g （N）對所有的 n≥ñ 0 。這個正式的定義解釋了為什麼我們不關心低階項（它們可以通過使 c 更大並且增加 n 0 ）和常數因子（c 項吸收它們） 來歸結。這種形式定義通常用於嚴格的演算法分析，但很少用於口語。