https://www.jianshu.com/p/f4cca5ce055a

我們假設(shè)計(jì)算機(jī)運(yùn)行一行基礎(chǔ)代碼需要執(zhí)行一次運(yùn)算。

int aFunc(void) {
    printf("Hello, World!\n");      //  需要執(zhí)行 1 次
    return 0;       // 需要執(zhí)行 1 次}

那么上面這個(gè)方法需要執(zhí)行 2 次運(yùn)算

int aFunc(int n) {
    for(int i = 0; i<n; i++) {         // 需要執(zhí)行 (n + 1) 次
        printf("Hello, World!\n");      // 需要執(zhí)行 n 次
    }
    return 0;       // 需要執(zhí)行 1 次}

這個(gè)方法需要 (n + 1 + n + 1) = 2n + 2 次運(yùn)算。

我們把 算法需要執(zhí)行的運(yùn)算次數(shù) 用 輸入大小n 的函數(shù) 表示，即 T(n) 。
此時(shí)為了 估算算法需要的運(yùn)行時(shí)間 和 簡化算法分析，我們引入時(shí)間復(fù)雜度的概念。

定義：存在常數(shù) c 和函數(shù) f(N)，使得當(dāng) N >= c 時(shí) T(N) <= f(N)，表示為 T(n) = O(f(n)) 。
如圖：

當(dāng) N >= 2 的時(shí)候，f(n) = n^2 總是大于 T(n) = n + 2 的，于是我們說 f(n) 的增長速度是大于或者等于 T(n) 的，也說 f(n) 是 T(n) 的上界，可以表示為 T(n) = O(f(n))。

因?yàn)閒(n) 的增長速度是大于或者等于 T(n) 的，即T(n) = O(f(n))，所以我們可以用 f(n) 的增長速度來度量 T(n) 的增長速度，所以我們說這個(gè)算法的時(shí)間復(fù)雜度是 O(f(n))。

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

顯然如果 T(n) = n^2，那么 T(n) = O(n^2)，T(n) = O(n^3)，T(n) = O(n^4) 都是成立的，但是因?yàn)榈谝粋€(gè) f(n) 的增長速度與 T(n) 是最接近的，所以第一個(gè)是最好的選擇，所以我們說這個(gè)算法的復(fù)雜度是 O(n^2) 。

那么當(dāng)我們拿到算法的執(zhí)行次數(shù)函數(shù) T(n) 之后怎么得到算法的時(shí)間復(fù)雜度呢？

1. 我們知道常數(shù)項(xiàng)對(duì)函數(shù)的增長速度影響并不大，所以當(dāng) T(n) = c，c 為一個(gè)常數(shù)的時(shí)候，我們說這個(gè)算法的時(shí)間復(fù)雜度為 O(1)；如果 T(n) 不等于一個(gè)常數(shù)項(xiàng)時(shí)，直接將常數(shù)項(xiàng)省略。

比如
第一個(gè) Hello, World 的例子中 T(n) = 2，所以我們說那個(gè)函數(shù)(算法)的時(shí)間復(fù)雜度為 O(1)。
T(n) = n + 29，此時(shí)時(shí)間復(fù)雜度為 O(n)。

1. 我們知道高次項(xiàng)對(duì)于函數(shù)的增長速度的影響是最大的。n^3 的增長速度是遠(yuǎn)超 n^2 的，同時(shí) n^2 的增長速度是遠(yuǎn)超 n 的。 同時(shí)因?yàn)橐蟮木炔桓?，所以我們直接忽略低此?xiàng)。

比如
T(n) = n^3 + n^2 + 29，此時(shí)時(shí)間復(fù)雜度為 O(n^3)。

1. 因?yàn)楹瘮?shù)的階數(shù)對(duì)函數(shù)的增長速度的影響是最顯著的，所以我們忽略與最高階相乘的常數(shù)。

比如
T(n) = 3n^3，此時(shí)時(shí)間復(fù)雜度為 O(n^3)。

綜合起來：如果一個(gè)算法的執(zhí)行次數(shù)是 T(n)，那么只保留最高次項(xiàng)，同時(shí)忽略最高項(xiàng)的系數(shù)后得到函數(shù) f(n)，此時(shí)算法的時(shí)間復(fù)雜度就是 O(f(n))。為了方便描述，下文稱此為 大O推導(dǎo)法。

由此可見，由執(zhí)行次數(shù) T(n) 得到時(shí)間復(fù)雜度并不困難，很多時(shí)候困難的是從算法通過分析和數(shù)學(xué)運(yùn)算得到 T(n)。對(duì)此，提供下列四個(gè)便利的法則，這些法則都是可以簡單推導(dǎo)出來的，總結(jié)出來以便提高效率。

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

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)。

1. 對(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)。

1. 對(duì)于順序執(zhí)行的語句或者算法，總的時(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)。

1. 對(duì)于條件判斷語句，總的時(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)向外分析，從最深層開始分析。如果遇到函數(shù)調(diào)用，要深入函數(shù)進(jìn)行分析。

最后，我們來練習(xí)一下

一. 基礎(chǔ)題
求該方法的時(shí)間復(fù)雜度

void aFunc(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            printf("Hello World\n");
        }
    }}

參考答案：
當(dāng) i = 0 時(shí)，內(nèi)循環(huán)執(zhí)行 n 次運(yùn)算，當(dāng) i = 1 時(shí)，內(nèi)循環(huán)執(zhí)行 n - 1 次運(yùn)算……當(dāng) i = n - 1 時(shí)，內(nèi)循環(huán)執(zhí)行 1 次運(yùn)算。
所以，執(zhí)行次數(shù) T(n) = n + (n - 1) + (n - 2)……+ 1 = n(n + 1) / 2 = n^2 / 2 + n / 2。
根據(jù)上文說的 大O推導(dǎo)法 可以知道，此時(shí)時(shí)間復(fù)雜度為 O(n^2)。

二. 進(jìn)階題
求該方法的時(shí)間復(fù)雜度

void aFunc(int n) {
    for (int i = 2; i < n; i++) {
        i *= 2;
        printf("%i\n", i);
    }}

參考答案：
假設(shè)循環(huán)次數(shù)為 t，則循環(huán)條件滿足 2^t < n。
可以得出，執(zhí)行次數(shù)t = log(2)(n)，即 T(n) = log(2)(n)，可見時(shí)間復(fù)雜度為 O(log(2)(n))，即 O(log n)。

三. 再次進(jìn)階
求該方法的時(shí)間復(fù)雜度

long aFunc(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }}

參考答案：
顯然運(yùn)行次數(shù)，T(0) = T(1) = 1，同時(shí) T(n) = T(n - 1) + T(n - 2) + 1，這里的 1 是其中的加法算一次執(zhí)行。
顯然 T(n) = T(n - 1) + T(n - 2) 是一個(gè)斐波那契數(shù)列，通過歸納證明法可以證明，當(dāng) n >= 1 時(shí) T(n) < (5/3)^n，同時(shí)當(dāng) n > 4 時(shí) T(n) >= (3/2)^n。
所以該方法的時(shí)間復(fù)雜度可以表示為 O((5/3)^n)，簡化后為 O(2^n)。
可見這個(gè)方法所需的運(yùn)行時(shí)間是以指數(shù)的速度增長的。如果大家感興趣，可以試下分別用 1，10，100 的輸入大小來測試下算法的運(yùn)行時(shí)間，相信大家會(huì)感受到時(shí)間復(fù)雜度的無窮魅力