時(shí)間復(fù)雜度

算法的時(shí)間復(fù)雜度，用來(lái)度量算法的運(yùn)行時(shí)間，記作: T(n) = O(f(n))。它表示隨著 輸入大小n 的增大，算法執(zhí)行需要的時(shí)間的增長(zhǎng)速度可以用 f(n) 來(lái)描述。

1. 對(duì)于一個(gè)循環(huán)，假設(shè)循環(huán)體的時(shí)間復(fù)雜度為O(n),循環(huán)次數(shù)為m，則這個(gè)循環(huán)的時(shí)間復(fù)雜度為O(nxm)

void aFunc(int n) {
    for(int i = 0; i < n; i++) {         // 循環(huán)次數(shù)為 n
        printf("Hello, World!\n");       // 循環(huán)體時(shí)間復(fù)雜度為 O(1)
    }
}

此時(shí)時(shí)間復(fù)雜度為 O(n × 1)，即 O(n)

2. 對(duì)于多個(gè)循環(huán)，假設(shè)循環(huán)體的時(shí)間復(fù)雜度為 O(n)，各個(gè)循環(huán)的循環(huán)次數(shù)分別是a, b, c...，則這個(gè)循環(huán)的時(shí)間復(fù)雜度為O(n×a×b×c...)。分析的時(shí)候應(yīng)該由里向外分析這些循環(huán)。

void aFunc(int n) {
    for(int i = 0; i < n; i++) {         // 循環(huán)次數(shù)為 n
        for(int j = 0; j < n; j++) {       // 循環(huán)次數(shù)為 n
            printf("Hello, World!\n");      // 循環(huán)體時(shí)間復(fù)雜度為 O(1)
        }
    }
}

此時(shí)時(shí)間復(fù)雜度為 O(n × n × 1)，即 O(n^2)。

3. 對(duì)于順序執(zhí)行的語(yǔ)句或者算法，總的時(shí)間復(fù)雜度等于其中最大的時(shí)間復(fù)雜度。

void aFunc(int n) {
    // 第一部分時(shí)間復(fù)雜度為 O(n^2)
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            printf("Hello, World!\n");
        }
    }
    // 第二部分時(shí)間復(fù)雜度為 O(n)
    for(int j = 0; j < n; j++) {
        printf("Hello, World!\n");
    }
}

此時(shí)時(shí)間復(fù)雜度為 max(O(n^2), O(n))，即 O(n^2)。

4. 對(duì)于條件判斷語(yǔ)句，總的時(shí)間復(fù)雜度等于其中時(shí)間復(fù)雜度最大的路徑的時(shí)間復(fù)雜度

void aFunc(int n) {
    if (n >= 0) {
        // 第一條路徑時(shí)間復(fù)雜度為 O(n^2)
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                printf("輸入數(shù)據(jù)大于等于零\n");
            }
        }
    } else {
        // 第二條路徑時(shí)間復(fù)雜度為 O(n)
        for(int j = 0; j < n; j++) {
            printf("輸入數(shù)據(jù)小于零\n");
        }
    }
}

此時(shí)時(shí)間復(fù)雜度為 max(O(n^2), O(n))，即 O(n^2)。

時(shí)間復(fù)雜度分析的基本策略是：從內(nèi)向外分析，從最深層開(kāi)始分析。如果遇到函數(shù)調(diào)用，要深入函數(shù)進(jìn)行分析。

參考

十分鐘從零搞定時(shí)間復(fù)雜度（計(jì)算算法的時(shí)間復(fù)雜度）

[1] 大話數(shù)據(jù)結(jié)構(gòu)

[2] 數(shù)據(jù)結(jié)構(gòu)與算法分析