程式, 演算法, 資料結構, C 語言

資料結構筆記(一)：演算法、時間複雜度、空間複雜度

資料結構，據說要學好程式只要學好資料結構和演算法就好了。但這明明是資料結構筆記啊，怎麼會提到時間複雜度呢？我也不知道，第一章就從時間複雜度和空間複雜度開始吧 XD

Nov 7, 2016 • 4 min read

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

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

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

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

時間複雜度

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

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

function(int n){
    print(n);
}

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

而下面這個演算法：

function(int n){
    for(i=0;i<n;i++){
        print(i);
    }
}

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

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

function(int n){
    for(i=0;i<n;i++){
        for(j=0;j<n-1;j++){
            print(i*j);
        }
    }
}

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

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

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

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

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

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

function(int n){
    for(int i=0;i<n;i++){
        print(i);
    }
}

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

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

function(int n){
    int c[n];
    for(int i=0;i<n;i++){
        c[i] = i;
    }
}

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

我們正降低廣告比例以提升閱讀體驗。如果你喜歡這篇文章，不妨按下 Like 按鈕或分享到社群，以行動支持我寫更多文章。當然，你也可以 點此用新臺幣支持我，或 點此透過 BTC、ETH、USDC 等加密貨幣支持我。

分享到：