Noob's Space

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

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

ds

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

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

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

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

時間複雜度

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

如果一個演算法執行的步驟是固定的,無關輸入的值而改變,那我們會記成 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*(n-1) = n2-n 次,但我們還是會記做 O(n2),也就是說,只要找出最高次方,並且把係數拿掉即可

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

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

空間複雜度

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

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

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

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

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

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

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

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

參考資料

複習一下?

資料結構筆記 目錄

廣告