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

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

輸入：一個算法應以待解決的問題的信息作為輸入。

輸出：輸入對應指令集處理后得到的信息。

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

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

確定性：算法對于特定的合法輸入，其對應的輸出是唯一的。即當算法從一個特定輸入開始，多次執(zhí)行同一指令集結果總是相同的。

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

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

一個用高級程序語言編寫的程序在計算機上運行式所消耗的時間取決于下列因素：

算法采用的策略、方法

問題的規(guī)模

書寫程序的語言

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

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

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

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

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

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

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

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

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

加法法則：總復雜度等于量級最大的那段代碼的復雜度

如果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)))

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

如果 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ù)量級遞增：
常量階 O(1)
對數(shù)階 O(logn)
線性階 O(n)
線性對數(shù)階 O(nlogn)
平方階 O(n^2)、立方階 O(n^3)、...k次方階 O(n^k)
指數(shù)階 O(2^n)
階乘階 O(n!)

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

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

下面結合簡單的代碼分析幾種常見的多項式時間復雜度：

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
    }
}

這段代碼的時間復雜度為O(1)。這段代碼執(zhí)行了100次，是一個常量的執(zhí)行時間，跟n的規(guī)模無關。即只要代碼的執(zhí)行時間不隨n的增長而增長，代碼的時間復雜度都記作為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ù)前面說到的算法分析原則，當n趨向于無窮大時，可以忽略低階項和最高項系數(shù)，則時間復雜度為O(n)。

O(logn)、O(nlogn)

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

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

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

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

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

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

如果一段代碼的時間復雜度是 O(logn)，我們循環(huán)執(zhí)行 n 遍，時間復雜度就是 O(nlogn) 了。而且，O(nlogn) 也是一種非常常見的算法時間復雜度。比如，歸并排序、快速排序的時間復雜度都是 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ī)則：嵌套代碼的復雜度等于嵌套內(nèi)外代碼復雜度的乘積。故時間復雜度為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 是表示兩個數(shù)據(jù)規(guī)模。我們無法事先評估 m 和 n 誰的量級大，所以我們在表示復雜度的時候，就不能簡單地利用加法法則，省略掉其中一個。所以，上面代碼的時間復雜度就是 O(m+n)。

空間復雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度。

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

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

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

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

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

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

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

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

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)在第一個元素，那就不需要繼續(xù)遍歷剩下的n-1個數(shù)據(jù)了，那么時間復雜度就是O(1)，為最好情況時間復雜度。但如果數(shù)組中不存在變量x，那我們就需要把整個數(shù)組遍歷一遍，時間復雜度就成O(n)，為最壞情況時間復雜度。故在不同情況下代碼的時間復雜度是不一樣的。

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

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

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

這個值為加權平均值，也叫期望值。所以平均時間復雜度的全稱應該叫加權平均時間復雜度或者期望時間復雜度。故這段代碼的平均時間復雜度為O(n)。

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

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

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

請看下面這段代碼：

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

在這段代碼中，當i

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

由此可知：

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

最壞情況時間復雜度為O(n);

平均情況時間復雜度為：

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

故平均時間復雜度為O(1)。

均攤復雜度：前n個操作復雜度都是O(1)，第n+1次操作的復雜度是O (n)，所以把最后一次的復雜度分攤到前n次上，那么均攤下來每次操作的復雜度為O(1)。

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

文章同步在微信公眾號，習慣微信上看文章的可以關注微信公眾號：加二減壹