教甄◆電腦科專業題庫下載題庫

而要評論一個演算法的好壞，最基本的方式就是計算它所使用的時間和空間。

演算法由三個部分組成：輸入、計算步驟、輸出，它是明確的、有限的、且有效率的。

註：演算法並不等於寫程式。
一個演算法除了可以虛擬碼或程式碼來記載，並編譯成電腦程式；也可以流程圖來記載，並設計成電子電路。

但一個演算法在不同效能的電腦上跑，可能會有不同的情況。所以我們用複雜度的方式來描述一算法的趨勢。簡單來說就是用比較科學的方法來描述演算法的可能複雜情況。

一個程式的時間複雜度是指完全地執行程式所需的計算機時間。

如果一個演算法執行的步驟是固定的，無關輸入的值而改變，那我們會記成 O(1)，例如：

不管 n 輸入多少，這個程式永遠只會執...

而要評論一個演算法的好壞，最基本的方式就是計算它所使用的時間和空間。

演算法由三個部分組成：輸入、計算步驟、輸出，它是明確的、有限的、且有效率的。

註：演算法並不等於寫程式。
一個演算法除了可以虛擬碼或程式碼來記載，並編譯成電腦程式；也可以流程圖來記載，並設計成電子電路。

但一個演算法在不同效能的電腦上跑，可能會有不同的情況。所以我們用複雜度的方式來描述一算法的趨勢。簡單來說就是用比較科學的方法來描述演算法的可能複雜情況。

時間複雜度

一個程式的時間複雜度是指完全地執行程式所需的計算機時間。

如果一個演算法執行的步驟是固定的，無關輸入的值而改變，那我們會記成 O(1)，例如：

不管 n 輸入多少，這個程式永遠只會執行一次。

而下面這個演算法：

這個演算法則是依據輸入的 n 的數量會跑 n 次，所以是 O(n)。

但還有某一些比較複雜的例子，例如：

這個演算法雖然跑了 n*(n-1) = n2-n 次，但我們還是會記做 O(n2)，也就是說，只要找出最高次方，並且把係數拿掉即可。

常見的時間複雜度還有：O(nlog(n))、O(n2)、O(2n)、O(n3)…等等，不用特別去記，只要大概的數一下迴圈數量，大致上判斷一下丟進去的變數會讓程式執行幾次即可。

註：大寫的英文字母 O 函數，代表演算法執行步驟數目上限

空間複雜度

而一個程式的空間複雜度是指完全地執行程式所需的記憶體量。

所需的記憶體量，大概可以看成所用的變數量。

例如下面這個函式，不管程式跑了幾遍，都不會影響使用的變數數量：

故該函式的空間複雜度記做 O(1)。

但下面這個函式，會隨著丟進去的數字而影響變數的量，例如：

丟進去 n，就換產生 n 個變數，故該函式空間複雜度為 O(n)。

資料來源：

https://noob.tw/data-structure