Asymptotic notation

Complexity (複雜度)

  • 描述每一種演算法的工作效率

  • 常見的複雜度類型

    • 1.Constant runtime (O(1))

      • 程式運作的時間不會隨著輸入的資料量改變而改變

    • 2.Linear runtime (O(n))

      • 單層迴圈

    • 3.Exponential runtime (O(n^2))

      • 隨著資料量的增加, 執行時間會以指數成長, 例如雙重迴圈

    • 4.Logarithmic runtime (O(Logn))

      • 隨著資料量增加, 執行時間雖然會增加, 但增加率會趨緩

Θ (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)

參考資料

PreviousLowest Common Ancestor (LCA)NextBinary search tree

Last updated