> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/notes-of-algorithms/asymptotic-notation.md).

# Asymptotic notation

## Complexity (複雜度)

* 描述每一種演算法的工作效率
* 常見的複雜度類型
  * 1.Constant runtime (O(1))
    * 程式運作的時間不會隨著輸入的資料量改變而改變
  * 2.Linear runtime (O(n))
    * 單層迴圈
  * 3.Exponential runtime (O(n^2))
    * 隨著資料量的增加, 執行時間會以指數成長, 例如雙重迴圈
  * 4.Logarithmic runtime (O(Logn))
    * 隨著資料量增加, 執行時間雖然會增加, 但增加率會趨緩

![圖片來源: https://zh.wikipedia.org/wiki/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6](/files/-LHYFRQX2TLLk6e7Jr4J)

## Θ (Theta) notation

* Θ (Theta) notation是一個集合, 用來描述趨勢之邊界
  * 例如Insertion sort在worse case的執行時間是 T(n) =  Θ(n^2)
* Definition
  *  Θ(g(n)) = { 存在有positive constant c1, c2, n0, 使f(n) 滿足0 ≤ c1g(n) ≤ f(n) ≤ c2g(n), n >= n0}
  * every member f(n)  ∈  Θ(g(n)) be **asymptotically nonnegative, that is, that f(n) be nonnegative whenever n is sufficient large.**
* g(n): **asymptotic tight bound** for f(n), g(n)是f(n)趨勢之邊界, 但不只一個:
  * g(n)函數其實可以把係數都提到c1,c2c1,c2裡,  以同一個函數：g(n)=n表示即可
  * &#x20;以上情況可以推廣至所有的**多項式(polynomial),** 以f(n)=3n^3+4n^2+5為例, 當n越來越大時, 對f(n)f之趨勢具有決定性影響力的是「最高次項」, 此例為「三次方項」, 所以f(n)的複雜度為Θ(n^3), 將係數拿進c1,c2, 便以**f(n)=Θ(n^3)**&#x8868;示 (參考自<http://alrightchiu.github.io/SecondRound/complexityasymptotic-notationjian-jin-fu-hao.html#tight>)

## O-notation

* O-notation用來描述上界(**asymptotic upper bound**), 也就是在worst case下的上限
* Definition
  * O(g(n)) = { 存在有positive constant c, n0, 使f(n) 滿足0 ≤ f(n) ≤ cg(n), n >= n0}
* O-notation常被拿來**僅依據演算法的整體結構來形容upper bound**
* O-notation與Θ notation的差異:
  * Insertion sort的O(n2)邊界指的是對所有的input的wort case running time
  * Insertion sort的Θ(n2)邊界指的並非是對所有的input的wort case running time, 例如, 如果拿一個sorted list做insertion sort, insertion sort只會執行在Θ(n)

## 參考資料

* <https://pjchender.blogspot.com/2017/09/big-o-notation-time-complexity.html>
* <http://alrightchiu.github.io/SecondRound/complexityasymptotic-notationjian-jin-fu-hao.html>