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

Θ (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表示即可

  • 以上情況可以推廣至所有的多項式(polynomial), 以f(n)=3n^3+4n^2+5為例, 當n越來越大時, 對f(n)f之趨勢具有決定性影響力的是「最高次項」, 此例為「三次方項」, 所以f(n)的複雜度為Θ(n^3), 將係數拿進c1,c2, 便以f(n)=Θ(n^3)表示 (參考自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