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

“二哥，為什么要講時(shí)間復(fù)雜度呀？”三妹問(wèn)。

“因?yàn)榻酉聛?lái)要用到啊。后面我們學(xué)習(xí) ArrayList、LinkedList 的時(shí)候，會(huì)比較兩者在增刪改查時(shí)的執(zhí)行效率，而時(shí)間復(fù)雜度是衡量執(zhí)行效率的一個(gè)重要標(biāo)準(zhǔn)。”我說(shuō)。

“到時(shí)候跑一下代碼，統(tǒng)計(jì)一下前后的時(shí)間差不更準(zhǔn)確嗎？”三妹反問(wèn)道。

“實(shí)際上，你說(shuō)的是另外一種評(píng)估方法，這種評(píng)估方法可以得出非常準(zhǔn)確的數(shù)值，但也有很大的局限性。”我不急不慢地說(shuō)。

第一，測(cè)試結(jié)果會(huì)受到測(cè)試環(huán)境的影響。你比如說(shuō)，同樣的代碼，在我這臺(tái) iMac 上跑出來(lái)的時(shí)間和在你那臺(tái)華為的 MacBook 上拋出的時(shí)間可能就差別很大。

第二，測(cè)試結(jié)果會(huì)受到測(cè)試數(shù)據(jù)的影響。你比如說(shuō)，一個(gè)排序后的數(shù)組和一個(gè)沒(méi)有排序后的數(shù)組，調(diào)用了同一個(gè)查詢(xún)方法，得出來(lái)的結(jié)果可能會(huì)差別特別大。

“因此，我們需要這種不依賴(lài)于具體測(cè)試環(huán)境和測(cè)試數(shù)據(jù)就能粗略地估算出執(zhí)行效率的方法，時(shí)間復(fù)雜度就是其中的一種，還有一種是空間復(fù)雜度。”我繼續(xù)補(bǔ)充道。

來(lái)看下面這段代碼：

public static int sum(int n) {
    int sum = 0; // 第 1 行
    for (int i=0;i<n;i++) { // 第 2 行
        sum = sum + 1; // 第 3 行
    } // 第 4 行
    return sum; // 第 5 行
}

這段代碼非常簡(jiǎn)單，方法體里總共 5 行代碼，包括“}”那一行。每段代碼的執(zhí)行時(shí)間可能都不大一樣，但假設(shè)我們認(rèn)為每行代碼的執(zhí)行時(shí)間是一樣的，比如說(shuō) unit_time，那么這段代碼總的執(zhí)行時(shí)間為多少呢？

“這個(gè)我知道呀！”三妹喊道，“第 1、5 行需要 2 個(gè) unit_time，第 2、3 行需要 2nunit_time，總的時(shí)間就是 2(n+1)*unit_time。”

“對(duì)，一段代碼的執(zhí)行時(shí)間 T(n) 和總的執(zhí)行次數(shù)成正比，也就是說(shuō)，代碼執(zhí)行的次數(shù)越多，花費(fèi)的時(shí)間就越多。”我總結(jié)道，“這個(gè)規(guī)律可以用一個(gè)公式來(lái)表達(dá)：”

T(n) = O(f(n))

f(n) 表示代碼總的執(zhí)行次數(shù)，大寫(xiě) O 表示代碼的執(zhí)行時(shí)間 T(n) 和 f(n) 成正比。

這也就是大 O 表示法，它不關(guān)心代碼具體的執(zhí)行時(shí)間是多少，它關(guān)心的是代碼執(zhí)行時(shí)間的變化趨勢(shì)，這也就是時(shí)間復(fù)雜度這個(gè)概念的由來(lái)。

對(duì)于上面那段代碼 sum() 來(lái)說(shuō)，影響時(shí)間復(fù)雜度的主要是第 2 行代碼，其余的，像系數(shù) 2、常數(shù) 2 都是可以忽略不計(jì)的，我們只關(guān)心影響最大的那個(gè)，所以時(shí)間復(fù)雜度就表示為 O(n)。

常見(jiàn)的時(shí)間復(fù)雜度有這么 3 個(gè)：

1）O(1)

代碼的執(zhí)行時(shí)間，和數(shù)據(jù)規(guī)模 n 沒(méi)有多大關(guān)系。

括號(hào)中的 1 可以是 3，可以是 5，可以 100，我們習(xí)慣用 1 來(lái)表示，表示這段代碼的執(zhí)行時(shí)間是一個(gè)常數(shù)級(jí)別。比如說(shuō)下面這段代碼：

int i = 0;
int j = 0;
int k = i + j;

實(shí)際上執(zhí)行了 3 次，但我們也認(rèn)為這段代碼的時(shí)間復(fù)雜度為 O(1)。

2）O(n)

時(shí)間復(fù)雜度和數(shù)據(jù)規(guī)模 n 是線(xiàn)性關(guān)系。換句話(huà)說(shuō)，數(shù)據(jù)規(guī)模增大 K 倍，代碼執(zhí)行的時(shí)間就大致增加 K 倍。

3）O(logn)

時(shí)間復(fù)雜度和數(shù)據(jù)規(guī)模 n 是對(duì)數(shù)關(guān)系。換句話(huà)說(shuō)，數(shù)據(jù)規(guī)模大幅增加時(shí)，代碼執(zhí)行的時(shí)間只有少量增加。

來(lái)看一下代碼示例，

public static void logn(int n) { 
    int i = 1;
    while (i < n) {
        i *= 2;
    }
}

換句話(huà)說(shuō)，當(dāng)數(shù)據(jù)量 n 從 2 增加到 2^64 時(shí)，代碼執(zhí)行的時(shí)間只增加 64 倍。

遍歷次數(shù) |   i
----------+-------
    0     |   i
    1     |  i*2
    2     |  i*4
   ...    |  ...
   ...    |  ...
    k     |  i*2^k 

“好了，三妹，這節(jié)就講到這吧，理解了上面 3 個(gè)時(shí)間復(fù)雜度，后面我們學(xué)習(xí) ArrayList、LinkedList 的時(shí)候，兩者在增刪改查時(shí)的執(zhí)行效率就很容易對(duì)比清楚了。”我抬起頭看了看三妹說(shuō)，她似乎有些明白，又有些不太明白。

“不要擔(dān)心哥，我再溫習(xí)一遍就能搞懂了。”三妹很乖。

PS：點(diǎn)擊「閱讀原文」可直達(dá)《教妹學(xué)Java》專(zhuān)欄的碼云在線(xiàn)地址，可以 star 安排一下了！

https://gitee.com/itwanger/jmx-java

三妹：給二哥點(diǎn)個(gè)贊吧，讓《教妹學(xué)Java》這么通俗易懂、風(fēng)趣幽默的 Java 教程被更多初學(xué)者看得到~