在系統(tǒng)分析算法的復雜度之前，我們先了解什么是算法？算法是指用來操作處理數(shù)據(jù)、解決程序問題的一組方法。但是對于同一個問題，我們去使用不同的算法，結果或許會一樣，但不同的地方就在于你所用算法所耗費的資源和時間，這就是我們接下來學習算法的原因，不同的算法，產生的效率也不同，我們需要從中找出最合適的算法。

復雜度的分析

一. 時間維度

是指執(zhí)行當前算法所消耗的時間，我們通常用時間復雜度來描述。

算法執(zhí)行時間需通過依據(jù)該算法編制的程序在計算機上運行時所消耗的時間來度量。而度量一個程序的執(zhí)行時間通常有兩種方法。

時間復雜度

定義：在進行算法分析時，語句總的執(zhí)行次數(shù)T(n)是關于問題規(guī)模n的函數(shù)，進而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級。算法的時間復雜度，也就是算法的時間量度。記作：T(n)=O(f(n))。它表示隨著問題規(guī)模n的擴大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間復雜度，簡稱為時間復雜度。其中f(n)是問題規(guī)模n的函數(shù)。

一般情況下，隨著輸入規(guī)模n的增加，T(n)增長最慢的算法為最優(yōu)算法。

常見的算法時間復雜度由小到大依次為：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

如何分析一個算法的時間復雜度呢？

用常數(shù)1取代運行時間中的所有的加法。在修改后的運行次數(shù)函數(shù)中，只保留最高階項。如果最高階項存在且不是1，則除去與這個項相乘的常數(shù)。得到的最后結果就是時間復雜度。

求解算法的時間復雜度的具體步驟

（1）找出算法中的基本語句；算法中執(zhí)行次數(shù)最多的那條語句就是基本語句，通常是最內層循環(huán)的循環(huán)體。

（2）計算基本語句的執(zhí)行次數(shù)的數(shù)量級；只需計算基本語句執(zhí)行次數(shù)的數(shù)量級，這就意味著只要保證基本語句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡化算法分析，并且使注意力集中在最重要的一點上：增長率。

（3）用大Ο記號表示算法的時間性能。將基本語句執(zhí)行次數(shù)的數(shù)量級放入大Ο記號中。

如果算法中包含嵌套的循環(huán)，則基本語句通常是最內層的循環(huán)體，如果算法中包含并列的循環(huán)，則將并列循環(huán)的時間復雜度相加。例如：

　　　for (i=1; i<=n; i++)
　　       x++;
　　for (i=1; i<=n; i++)
　     　for (j=1; j<=n; j++)
　　          x++;

第一個for循環(huán)的時間復雜度為Ο(n)，第二個for循環(huán)的時間復雜度為Ο(n2)，則整個算法的時間復雜度為Ο(n+n2)=Ο(n2)。

Ο(1)表示基本語句的執(zhí)行次數(shù)是一個常數(shù)，一般來說，只要算法中不存在循環(huán)語句，其時間復雜度就是Ο(1)。其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項式時間，而Ο(2n)和Ο(n!)稱為指數(shù)時間。計算機科學家普遍認為前者（即多項式時間復雜度的算法）是有效算法，把這類問題稱為P（Polynomial,多項式）類問題，而把后者（即指數(shù)時間復雜度的算法）稱為NP（Non-Deterministic Polynomial, 非確定多項式）問題。

（4）在計算算法時間復雜度時有以下幾個簡單的程序分析法則:

1. 對于一些簡單的輸入輸出語句或賦值語句,近似認為需要O(1)時間

2. 對于順序結構,需要依次執(zhí)行一系列語句所用的時間可采用大O下"求和法則"

求和法則:是指若算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1(n)+T2(n)=O(max(f(n),g(n)))

特別地，若T1(m)=O(f(m)), T2(n)=O(g(n))，則 T1(m)+T2(n)=O(f(m) + g(n))

3. 對于選擇結構,如if語句,它的主要時間耗費是在執(zhí)行then字句或else字句所用的時間,需注意的是檢驗條件也需要O(1)時間

4. 對于循環(huán)結構,循環(huán)語句的運行時間主要體現(xiàn)在多次迭代中執(zhí)行循環(huán)體以及檢驗循環(huán)條件的時間耗費,一般可用大O下"乘法法則"

乘法法則: 是指若算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1*T2=O(f(n)*g(n))

5. 對于復雜的算法,可以將它分成幾個容易估算的部分,然后利用求和法則和乘法法則技術整個算法的時間復雜度

另外還有以下2個運算法則:(1) 若g(n)=O(f(n)),則O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一個正常數(shù)

二、空間維度

類似于時間復雜度的討論，一個算法的空間復雜度S(n)定義為該算法所耗費的存儲空間，它也是問題規(guī)模n的函數(shù)。漸近空間復雜度也常常簡稱為空間復雜度。

空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的一個量度，同樣反映的是一個趨勢，我們用S(n)來定義。

空間復雜度

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

和時間復雜度類似，空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的度量，也是使用大O表示法。

（1）常量空間：存儲空間大小固定，和輸入沒有關系時，空間復雜度是O(1)

（2）線性空間：算法中定義了一個線性集合，如一個列表，并且集合大小和輸入規(guī)模n成正比，空間復雜度記為O(n)

（3）二維空間：算法中定義了一個二維列表集合，并且集合的長和寬都和輸入規(guī)模n成正比，空間復雜度記為O(nn)/O（nm)

（4）遞歸空間：遞歸過程就是一個進棧和出棧的過程，當進入一個新函數(shù)時，進行入棧操作，把調用的函數(shù)和參數(shù)信息壓入棧中；當函數(shù)返回時，執(zhí)行出棧。遞歸的空間復雜度也是線性的，如果遞歸的深度是n，那么空間復雜度就是O(n)。

以上就是關于復雜度的內容，總的來說，衡量不同算法的優(yōu)劣，主要還是根據(jù)算法所占的空間和時間兩個維度去考慮。世界上沒有絕對完美的事情，總會有很多缺憾，而我們要做的就是在其中找出最適合的解決方案。