演算法的「時間複雜度 O（n）」

【定義】O（n）可視為某演算法在電腦中所需執行時間，亦即將「執行次數」轉換成電腦所需的執行時間。

【執行次數轉換時間複雜度之作法】

取「執行次數」中最高次方或最大指數部份的項目即可。

(1)陣列元素相加為2n+3=0（n）

(2)矩陣相加為2n^2+2n+2=0（n^2）

(3)矩陣相乘為2n^3+4n^2+2n+2=0（n^3）

時間複雜度的等級

【定義】在資料結構中，評估某一演算法的執行效率，必須視其時間複雜度的等級。

【時間複雜度的等級】(效率由高至低排列）

O(1) : 常數時間(Constant Time)

O(log2n）：次線性時間（Sub-linear）

O（n）：線性時間（Linear）

O（nlog2n）：線性乘對數時間

O（n^2）：平方時間（Quadratic）

O（n^3）：立方時間（Cubic）

O（2^n）：指數時間（Exponential）

O（n!）：階乘時間（Factorial）

說明：效率愈高，代表著執行時間愈短。

例如O（n）比O（n^2）更有效率

空間複雜度（SPACE COMPLEXITY）

【定義】
一個程式P的空間複雜度（Space Complexity）包含固定的空間需求與變動的空間需求兩個部分。

固定的空間需求

【定義】
包含了程式在編譯時期所產生的空間需求。

例如程式本身的指令、常數、靜態變數及結構等。

變動空間需求

【定義】
是指從呼叫該副程式開始到完成之過程，所有佔用的「記憶體空間」

例如：參數、變數宣告，回傳值以及傳回位址時，都會佔用記憶體空間。