演算法定義

演算法筆記 1 – 演算法定義與 Big O Notation

1. 演算法定義

一般來說,符合以下這 5 種特性(Characteristics)就可以稱為演算法:

1.1 輸入(Input)

An algorithm may have many inputs or no inputs at all.

演算法應該具有 0 個或多個輸入。

1.2 輸出(Output)

An algorithm should result at least one output.

演算法至少要有一個或多個輸出,不允許 0 個輸出。

1.3 有限性(Finiteness)

An algorithm should have finite number of steps and it should end after a finite time.

演算法需要在有限的步驟及有限的時間內完成,不能有無窮迴圈。

1.4 明確性(Definiteness)

Each step must be clear, well-defined and precise. There should be no any ambiguity.

演算法的每個步驟地須清楚定義,不允許有模糊的空間。

1.5 有效性(Effectiveness)

The algorithm should be possible and practicable in real life. It should not be abstract or imaginary.

演算法的每個步驟都必須是有效的且可在有限的次數內執行完成。

2. Big O Notation

Big O notation 是用來分析演算法效率的數學符號。

在分析一個 f(n) 的演算法時,都是以 n 趨近於極限來考量,因此會以以下原則來計算 Big O:

2.1 只保留最高次項

f(n) = n3 + 100n2 + 50n + 9 的 Big O 是 n3,也可以寫作 O(n3)

2.2 常數項降為 1

f(n) = 20n3 + 100n2 + 50n + 9 => O(n3)

f(n) = 50 => O(1)

2.3 log 省略底數

f(n) = log2n => O(logn)

常見的 Big O 比較:

O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n!)

3. 參考資料

Algorithms (Characteristics, Guidelines & Advantages)
What is an Algorithm? Types, Applications, and Characteristics
演算法- 維基百科,自由的百科全書
Algorithm characterizations – Wikipedia

如果覺得我的文章有幫助的話,歡迎幫我的粉專按讚哦~謝謝你!

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top