摘要：平均情況時(shí)間復(fù)雜度用代碼在所有情況下執(zhí)行的次數(shù)的加權(quán)平均值表示，簡稱平均時(shí)間復(fù)雜度。故平均時(shí)間復(fù)雜度的計(jì)算為查找需要遍歷的元素個(gè)數(shù)乘以相應(yīng)的權(quán)術(shù)這個(gè)值為加權(quán)平均值，也叫期望值。

算法（algorithm）是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作；此外，一個(gè)算法通常來說具有以下五個(gè)特性：

輸入：一個(gè)算法應(yīng)以待解決的問題的信息作為輸入。

輸出：輸入對(duì)應(yīng)指令集處理后得到的信息。

有窮性：算法執(zhí)行的指令個(gè)數(shù)是有限的，每個(gè)指令又是在有限時(shí)間內(nèi)完成的，因此整個(gè)算法也是在有限時(shí)間內(nèi)可以結(jié)束的。

可行性：算法是可行的，即算法中的每一條指令都是可以實(shí)現(xiàn)的，均能在有限的時(shí)間內(nèi)完成。

確定性：算法對(duì)于特定的合法輸入，其對(duì)應(yīng)的輸出是唯一的。即當(dāng)算法從一個(gè)特定輸入開始，多次執(zhí)行同一指令集結(jié)果總是相同的。

這種方法有兩個(gè)缺陷：一是必須先運(yùn)行一句算法編制的程序；二是所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件、軟件、等環(huán)境因素，有時(shí)容易掩蓋算法本身的優(yōu)勢(shì)。故一般采用事前估算的方法。

一個(gè)算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)3種）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的，則算法時(shí)間取決于兩者的綜合效果。為了便于比較同一個(gè)問題的不同算法，通常的做法是，從算法中選取一種對(duì)于所研究的問題（或算法類型）來說是基本操作的原操作，以該基本操作的重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度。

一個(gè)用高級(jí)程序語言編寫的程序在計(jì)算機(jī)上運(yùn)行式所消耗的時(shí)間取決于下列因素：

算法采用的策略、方法

問題的規(guī)模

書寫程序的語言

編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量

機(jī)器執(zhí)行指令的速度

漸進(jìn)時(shí)間復(fù)雜度(asymptotic time complexity):若存在函數(shù)f(n)，使得當(dāng)n趨近于無窮大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同量級(jí)函數(shù)。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。漸進(jìn)時(shí)間復(fù)雜度用大寫O來表示，所以也被稱為大O表示法。

T(n)=O(f(n))這個(gè)公式中，T(n)表示代碼的執(zhí)行時(shí)間；n表示數(shù)據(jù)規(guī)模的大小；f(n)表示每行代碼執(zhí)行的次數(shù)總和。因?yàn)檫@是一個(gè)公式，所以用f(n)來表示，公式中的O表示漸進(jìn)于無窮的一種行為。大O時(shí)間復(fù)雜度實(shí)際上并不具體表示代碼真正的執(zhí)行時(shí)間，而是表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長的變化趨勢(shì)。

如果運(yùn)行時(shí)間是常數(shù)量級(jí)，用常數(shù)1表示。

只保留時(shí)間函數(shù)中的最高階項(xiàng)

如果最高階項(xiàng)存在，則省去最高階項(xiàng)前面的系數(shù)。

或者換種說法：在”公式中的低階、常量、系數(shù)三部分并不左右增長趨勢(shì)，所以都可以忽略“基礎(chǔ)上，

只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼

加法法則：總復(fù)雜度等于量級(jí)最大的那段代碼的復(fù)雜度

如果T1(n)=O(f(n))，T2(n)=O(g(n));

那么T(n)=T1(n)+T2(n)=max(O(f(n)),O(g(n)))=O(max(f(n),g(n)))

乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積

如果 T1(n)=O(f(n))，T2(n)=O(g(n))；

那么 T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)g(n))；

按數(shù)量級(jí)遞增：
常量階 O(1)
對(duì)數(shù)階 O(logn)
線性階 O(n)
線性對(duì)數(shù)階 O(nlogn)
平方階 O(n^2)、立方階 O(n^3)、...k次方階 O(n^k)
指數(shù)階 O(2^n)
階乘階 O(n!)

對(duì)于上述羅列的復(fù)雜度量級(jí)，可以分為：多項(xiàng)式量級(jí)和非多項(xiàng)式量級(jí)。其中，非多項(xiàng)式量級(jí)只有兩個(gè)：指數(shù)階 O(2ⁿ)和階乘階 O(n!)。

我們把時(shí)間復(fù)雜度為非多項(xiàng)式量級(jí)的算法問題叫作NP（Non-Deterministic Polynomial，非確定多項(xiàng)式）問題。當(dāng)數(shù)據(jù)規(guī)模 n 越來越大時(shí)，非多項(xiàng)式量級(jí)算法的執(zhí)行時(shí)間會(huì)急劇增加，求解問題的執(zhí)行時(shí)間會(huì)無限增長。所以，非多項(xiàng)式時(shí)間復(fù)雜度的算法其實(shí)是非常低效的算法。

下面結(jié)合簡單的代碼分析幾種常見的多項(xiàng)式時(shí)間復(fù)雜度：

O(1)

public void fun(){//沒有入?yún)⒆兞?    int sum = 0;//執(zhí)行次數(shù)：1
    int p = 1;//執(zhí)行次數(shù)：1
    for(; p <= 100; ++p){//執(zhí)行次數(shù)為：100
        sum = sum + p;//執(zhí)行次數(shù)為：100
    }
}

這段代碼的時(shí)間復(fù)雜度為O(1)。這段代碼執(zhí)行了100次，是一個(gè)常量的執(zhí)行時(shí)間，跟n的規(guī)模無關(guān)。即只要代碼的執(zhí)行時(shí)間不隨n的增長而增長，代碼的時(shí)間復(fù)雜度都記作為O(1)。

O(n)

public void fun(){
    int n = 100;//執(zhí)行次數(shù)：1
    int sum = 0;//執(zhí)行次數(shù)：1
    for(int j = 1; j <= n; ++j){//執(zhí)行次數(shù)：n
        sum += j;//執(zhí)行次數(shù)：n
    }
}

即T(n)=1+1+n+n=2n+2，根據(jù)前面說到的算法分析原則，當(dāng)n趨向于無窮大時(shí)，可以忽略低階項(xiàng)和最高項(xiàng)系數(shù)，則時(shí)間復(fù)雜度為O(n)。

O(logn)、O(nlogn)

int i = 1;
while (i <= n) {
    i = i * 2;
}

實(shí)際上，我們只需找出循環(huán)執(zhí)行次數(shù)最多的代碼，求出該代碼被執(zhí)行了多少次，就能知道整段代碼的時(shí)間復(fù)雜度。從代碼中可以看出，變量i的值從1開始，每循環(huán)一次乘以2，實(shí)際上i的取值是一個(gè)等比數(shù)列。通過2^x=n，求出x=log₂n，所以這段代碼的時(shí)間復(fù)雜度為O(log₂n)。

int i = 1;
while (i <= n) {
    i = i * 3;
}

根據(jù)上述思路，得出這段代碼的時(shí)間復(fù)雜度為O(log₃n))。

實(shí)際上，不管是以 2 為底、以 3 為底，還是以 10 為底，我們可以把所有對(duì)數(shù)階的時(shí)間復(fù)雜度都 記為 O(logn)。

我們知道，對(duì)數(shù)之間是可以互相轉(zhuǎn)換的，log n 就等于 log 2  log n，所以 O(log n) = O(C  log n)，其中 C=log 2 是一個(gè)常量。基于我們前面的一個(gè)理論：在采用大 O 標(biāo)記復(fù)雜度的時(shí) 候，可以忽略系數(shù)，即 O(Cf(n)) = O(f(n))。所以，O(log n) 就等于 O(log n)。因此，在對(duì)數(shù)階 時(shí)間復(fù)雜度的表示方法里，我們忽略對(duì)數(shù)的“底”，統(tǒng)一表示為 O(logn)。

如果一段代碼的時(shí)間復(fù)雜度是 O(logn)，我們循環(huán)執(zhí)行 n 遍，時(shí)間復(fù)雜度就是 O(nlogn) 了。而且，O(nlogn) 也是一種非常常見的算法時(shí)間復(fù)雜度。比如，歸并排序、快速排序的時(shí)間復(fù)雜度都是 O(nlogn)。

O(n²)

public void fun(){
    int n = 100;//執(zhí)行次數(shù)：1
    int sum = 0;//執(zhí)行次數(shù)：1
    for(int i = 1; i <= n; ++i){//執(zhí)行次數(shù)：n
        for(int j = 1; j <= n; ++j){//執(zhí)行次數(shù)n*n
            sum += j;//執(zhí)行次數(shù)n*n
        }
    }
}

根據(jù)乘法規(guī)則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積。故時(shí)間復(fù)雜度為O(n²)。

O(m+n)

public int fun(int m, int n){
    int sum1 = 0;
    int i = 1;
    for(; i < m; ++i){
        sum1 = sum1 + i;
    }
    
    int sum2 = 0;
    int j = 1;
    for(; j < n; ++j){
        sum2 = sum2 + j;
    }
    return sum1 + sum2;
}

從代碼中可以看出，m 和 n 是表示兩個(gè)數(shù)據(jù)規(guī)模。我們無法事先評(píng)估 m 和 n 誰的量級(jí)大，所以我們?cè)诒硎緩?fù)雜度的時(shí)候，就不能簡單地利用加法法則，省略掉其中一個(gè)。所以，上面代碼的時(shí)間復(fù)雜度就是 O(m+n)。

空間復(fù)雜度(Space Complexity)是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度。

算法的空間復(fù)雜度通過計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)，算法的空間復(fù)雜度的計(jì)算公式記作：S(n)=O(f(n))，其中，n為問題的規(guī)模，f(n)為語句關(guān)于n所占存儲(chǔ)空間的函數(shù)。

程序執(zhí)行時(shí)所需存儲(chǔ)空間包括以下兩部分。　　
（1）固定部分。這部分空間的大小與輸入/輸出的數(shù)據(jù)的個(gè)數(shù)多少、數(shù)值無關(guān)。主要包括指令空間（即代碼空間）、數(shù)據(jù)空間（常量、簡單變量）等所占的空間。這部分屬于靜態(tài)空間。
（2）可變空間，這部分空間的主要包括動(dòng)態(tài)分配的空間，以及遞歸棧所需的空間等。這部分的空間大小與算法有關(guān)。

一個(gè)算法的空間復(fù)雜度只考慮在運(yùn)行過程中為局部變量分配的存儲(chǔ)空間的大小，它包括為參數(shù)表中形參變量分配的存儲(chǔ)空間和為在函數(shù)體中定義的局部變量分配的存儲(chǔ)空間兩個(gè)部分。

public void fun(int n){
    int[] a = new int[n];
    for(int i = 1; i < n; ++i){
        a[i] = i * i;
    }
}

從代碼中可以看出，申請(qǐng)了一個(gè)空間存儲(chǔ)變量i，但是它是常量階的，跟數(shù)據(jù)規(guī)模n無關(guān)。第二行代碼為申請(qǐng)了一個(gè)大小為n的int類型數(shù)組，除此之外，沒有占用更多的空間，所以整段代碼的空間復(fù)雜度就是O(n)。

最好情況時(shí)間復(fù)雜度：代碼在最理想情況下執(zhí)行的時(shí)間復(fù)雜度。

最壞情況時(shí)間復(fù)雜度：代碼在最壞情況下執(zhí)行的時(shí)間復(fù)雜度。

平均情況時(shí)間復(fù)雜度：用代碼在所有情況下執(zhí)行的次數(shù)的加權(quán)平均值表示，簡稱平均時(shí)間復(fù)雜度。

public int find(int[] array, int n. int x){
    int index = -1;
    for(int i = 0; i < n; ++i){
        if(array[i] == x){
            index = i;
            break;
        }
    }
    return index;
}

在這段代碼中，如果要查找的變量x出現(xiàn)在第一個(gè)元素，那就不需要繼續(xù)遍歷剩下的n-1個(gè)數(shù)據(jù)了，那么時(shí)間復(fù)雜度就是O(1)，為最好情況時(shí)間復(fù)雜度。但如果數(shù)組中不存在變量x，那我們就需要把整個(gè)數(shù)組遍歷一遍，時(shí)間復(fù)雜度就成O(n)，為最壞情況時(shí)間復(fù)雜度。故在不同情況下代碼的時(shí)間復(fù)雜度是不一樣的。

最好情況時(shí)間復(fù)雜度和最壞情況時(shí)間復(fù)雜度都是在極端情況下的代碼時(shí)間復(fù)雜度，發(fā)生的概率不大。為了更好地表示平均情況下的復(fù)雜度，我們需要引入一個(gè)新的概念：平均時(shí)間復(fù)雜度。

在這段代碼中，要查找的變量x在數(shù)組中的位置有n+1中情況：在數(shù)組的0~n-1位置中和不在數(shù)組中。假設(shè)在數(shù)組中和不在數(shù)組中的概率都為1/2；變量x出現(xiàn)在0~n-1這n個(gè)位置的概率為1/n，根據(jù)概率乘法規(guī)則，要查找的數(shù)據(jù)出現(xiàn)在0~n-1中任意位置的概率為1/(2n)。故平均時(shí)間復(fù)雜度的計(jì)算為：（查找需要遍歷的元素個(gè)數(shù)乘以相應(yīng)的權(quán)術(shù)）

$$ 1*1/(2n)+2*1/(2n)+3*1/(2n)+···+n*1/(2n)+n*1/2=(3n+1)/4 $$

這個(gè)值為加權(quán)平均值，也叫期望值。所以平均時(shí)間復(fù)雜度的全稱應(yīng)該叫加權(quán)平均時(shí)間復(fù)雜度或者期望時(shí)間復(fù)雜度。故這段代碼的平均時(shí)間復(fù)雜度為O(n)。

加權(quán)平均值即將各數(shù)值乘以相應(yīng)的權(quán)數(shù)，然后加總求和得到總體值，再除以總的單位數(shù)。

在大多數(shù)情況下，我們并不需要區(qū)分最好、最壞、平均情況時(shí)間復(fù)雜度三種情況。我們使用一個(gè)復(fù)雜度就可以滿足需求了。只有同一塊代碼在不同的情況下，時(shí)間復(fù)雜度有量級(jí)的差距，我們才會(huì)使用這三種復(fù)雜度表示法來區(qū)分。

對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行一組連續(xù)操作中，大部分情況下時(shí)間復(fù)雜度都很低，只有個(gè)別情況下時(shí)間復(fù)雜度比較高，而且這些操作之間存在前后連貫的時(shí)序關(guān)系，這個(gè)時(shí)候，我們就可以將這一組操作放在一塊兒分析，看是否能將較高時(shí)間復(fù)雜度那次操作的耗時(shí)，平攤到其他那些時(shí)間復(fù)雜度比較低的操作上。而且，在能夠應(yīng)用均攤時(shí)間復(fù)雜度分析的場合，一般均攤時(shí)間復(fù)雜度就等于最好情況時(shí)間復(fù)雜度。

請(qǐng)看下面這段代碼：

int[] array = new int[10];//聲明一個(gè)大小為10的數(shù)組array
int length = 10;
int i = 0;
//往數(shù)組里添加一個(gè)元素
public void addElement(int element){
    if(i > = len){
        int[] new_array = new int[len*2];
        for(int j = 0; j < len; ++j){
            //復(fù)制數(shù)據(jù)到new_array數(shù)組中
            new_array[j] = array[j];
        }
        array = new_array;
        len = len * 2;
    }
    //將element插入到下標(biāo)為i的位置
    array[i] = element;
    ++i;
}

在這段代碼中，當(dāng)i

當(dāng)i>=len時(shí)，即當(dāng)i=n時(shí)，for循環(huán)進(jìn)行數(shù)組的復(fù)制，只有這一次的時(shí)間復(fù)雜度為O(n)。

由此可知：

該算法的最好情況時(shí)間復(fù)雜度為O(1);

最壞情況時(shí)間復(fù)雜度為O(n);

平均情況時(shí)間復(fù)雜度為：

$$ 1*1/(n+1)+1*1/(n+1)+···+1*1/(n+1)+n*1/(n+1)=2n/(n+1) $$

故平均時(shí)間復(fù)雜度為O(1)。

均攤復(fù)雜度：前n個(gè)操作復(fù)雜度都是O(1)，第n+1次操作的復(fù)雜度是O (n)，所以把最后一次的復(fù)雜度分?jǐn)偟角皀次上，那么均攤下來每次操作的復(fù)雜度為O(1)。

總結(jié)：漸進(jìn)式時(shí)間，空間復(fù)雜度分析只是一個(gè)理論模型，只能提供給粗略的估計(jì)分析，一個(gè)低階的時(shí)間復(fù)雜度程序有極大的可能性會(huì)優(yōu)于一個(gè)高階的時(shí)間復(fù)雜度程序，針對(duì)不同的宿主環(huán)境，不同的數(shù)據(jù)集，不同的數(shù)據(jù)量的大小，在實(shí)際應(yīng)用上面可能真正的性能會(huì)不同。針對(duì)不同的實(shí)際情況， 進(jìn)而進(jìn)行一定的性能基準(zhǔn)測試是很有必要的，進(jìn)而選擇適合特定應(yīng)用場景下的最優(yōu)算法。

文章同步在微信公眾號(hào)，習(xí)慣微信上看文章的可以關(guān)注微信公眾號(hào)：加二減壹