算法復(fù)雜度
- 時(shí)間復(fù)雜度
- 空間復(fù)雜度
什么是時(shí)間復(fù)雜度
算法執(zhí)行時(shí)間需通過依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間來度量
怎么度量程序執(zhí)行時(shí)間
- 事后統(tǒng)計(jì)的方法
這種方法可行，但不是一個(gè)好的方法呜师。該方法有兩個(gè)缺陷：一是要想對(duì)設(shè)計(jì)的算法的運(yùn)行性能進(jìn)行評(píng)測(cè)蝶押，必須先依據(jù)算法編制相應(yīng)的程序并實(shí)際運(yùn)行浦楣；二是所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件袖肥、軟件等環(huán)境因素，有時(shí)容易掩蓋算法本身的優(yōu)勢(shì)振劳。 - 事前分析估算的方法
因事后統(tǒng)計(jì)方法更多的依賴于計(jì)算機(jī)的硬件椎组、軟件等環(huán)境因素，有時(shí)容易掩蓋算法本身的優(yōu)劣历恐。因此人們常常采用事前分析估算的方法寸癌。
決定時(shí)間消耗的因素
- 算法采用的策略、方法
- 編譯產(chǎn)生的代碼質(zhì)量
- 問題的輸入規(guī)模
- 機(jī)器執(zhí)行指令的速度弱贼。
具體度量方式
- 一個(gè)算法是由控制結(jié)構(gòu)（順序蒸苇、分支和循環(huán)3種）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的，則算法時(shí)間取決于兩者的綜合效果吮旅。為了便于比較同一個(gè)問題的不同算法溪烤，通常的做法是，從算法中選取一種對(duì)于所研究的問題（或算法類型）來說是基本操作的原操作庇勃，以該基本操作的重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度檬嘀。
時(shí)間復(fù)雜度與時(shí)間頻度
- 時(shí)間頻度
- 時(shí)間復(fù)雜度
時(shí)間頻度
- 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來的责嚷，必須上機(jī)運(yùn)行測(cè)試才能知道鸳兽。但我們不可能也沒有必要對(duì)每個(gè)算法都上機(jī)測(cè)試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多罕拂，哪個(gè)算法花費(fèi)的時(shí)間少就可以了贸铜。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語句執(zhí)行次數(shù)多聂受，它花費(fèi)時(shí)間就多。一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度烤镐。記為T(n)蛋济。
時(shí)間復(fù)雜度
在剛才提到的時(shí)間頻度中，n稱為問題的規(guī)模炮叶，當(dāng)n不斷變化時(shí)碗旅，時(shí)間頻度T(n)也會(huì)不斷變化。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律祟辟。為此侣肄，我們引入時(shí)間復(fù)雜度概念。 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)吼具，用T(n)表示僚纷，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí)拗盒，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)陡蝇。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度痊臭，簡(jiǎn)稱時(shí)間復(fù)雜度。
T (n) = Ο(f (n)) 表示存在一個(gè)常數(shù)C登夫，使得在當(dāng)n趨于正無窮時(shí)總有 T (n) ≤ C * f(n)悼嫉。簡(jiǎn)單來說，就是T(n)在n趨于正無窮時(shí)最大也就跟f(n)差不多大戏蔑。也就是說當(dāng)n趨于正無窮時(shí)T (n)的上界是C * f(n)总棵。其雖然對(duì)f(n)沒有規(guī)定鳍寂，但是一般都是取盡可能簡(jiǎn)單的函數(shù)迄汛。例如骤视，O(2n2+n +1) = O (3n2+n+3) = O (7n2 + n) = O ( n2 ) ，一般都只用O(n2)表示就可以了睹逃。注意到大O符號(hào)里隱藏著一個(gè)常數(shù)C祷肯，所以f(n)里一般不加系數(shù)。如果把T(n)當(dāng)做一棵樹翼闹，那么O(f(n))所表達(dá)的就是樹干蒋纬，只關(guān)心其中的主干坚弱，其他的細(xì)枝末節(jié)全都拋棄不管史汗。
Landau符號(hào):上面的O是符號(hào)中的一個(gè)
- Landau符號(hào)是由德國(guó)數(shù)論學(xué)家保羅·巴赫曼（Paul Bachmann）在其1892年的著作《解析數(shù)論》首先引入拒垃，由另一位德國(guó)數(shù)論學(xué)家艾德蒙·朗道（Edmund Landau）推廣。Landau符號(hào)的作用在于用簡(jiǎn)單的函數(shù)來描述復(fù)雜函數(shù)行為戈毒，給出一個(gè)上或下（確）界。在計(jì)算算法復(fù)雜度時(shí)一般只用到大O符號(hào)横堡，Landau符號(hào)體系中的小o符號(hào)命贴、Θ符號(hào)等等比較不常用。這里的O污茵，最初是用大寫希臘字母葬项，但現(xiàn)在都用大寫英語字母O；小o符號(hào)也是用小寫英語字母o襟士，Θ符號(hào)則維持大寫希臘字母Θ嚷量。
常見的時(shí)間復(fù)雜度
在各種不同算法中，若算法中語句執(zhí)行次數(shù)為一個(gè)常數(shù)嗜历，則時(shí)間復(fù)雜度為O(1),另外身坐，在時(shí)間頻度不相同時(shí)部蛇，時(shí)間復(fù)雜度有可能相同咐蝇，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時(shí)間復(fù)雜度相同抹腿，都為O(n2)。 按數(shù)量級(jí)遞增排列崇败，常見的時(shí)間復(fù)雜度有：常數(shù)階O(1),對(duì)數(shù)階O(log2n),線性階O(n), 線性對(duì)數(shù)階O(nlog2n),平方階O(n2)肩祥，立方階O(n3),...混狠， k次方階O(nk),指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大泡徙，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。
常見的算法時(shí)間復(fù)雜度由小到大依次為：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
求解時(shí)間復(fù)雜度的步驟
- 找出算法中的基本語句；
算法中執(zhí)行次數(shù)最多的那條語句就是基本語句色鸳，通常是最內(nèi)層循環(huán)的循環(huán)體坠七。 - 計(jì)算基本語句的執(zhí)行次數(shù)的數(shù)量級(jí)；
只需計(jì)算基本語句執(zhí)行次數(shù)的數(shù)量級(jí)拄踪，這就意味著只要保證基本語句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可惶桐，可以忽略所有低次冪和最高次冪的系數(shù)潘懊。這樣能夠簡(jiǎn)化算法分析，并且使注意力集中在最重要的一點(diǎn)上：增長(zhǎng)率救恨。 - 用大Ο記號(hào)表示算法的時(shí)間性能释树。
將基本語句執(zhí)行次數(shù)的數(shù)量級(jí)放入大Ο記號(hào)中。
計(jì)算時(shí)間復(fù)雜度示例：
- 原則
如果算法中包含嵌套的循環(huán)秸仙，則基本語句通常是最內(nèi)層的循環(huán)體寂纪，如果算法中包含并列的循環(huán)，則將并列循環(huán)的時(shí)間復(fù)雜度相加抢腐。 - 示例
for (int i = 1; i <= n; i++)
x++;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
x++;
- 分析
第一個(gè)for循環(huán)的時(shí)間復(fù)雜度為Ο(n)襟交，第二個(gè)for循環(huán)的時(shí)間復(fù)雜度為Ο(n2)捣域，則整個(gè)算法的時(shí)間復(fù)雜度為Ο(n+n2)=Ο(n2)。
PS:
Ο(1)表示基本語句的執(zhí)行次數(shù)是一個(gè)常數(shù)迹鹅，一般來說贞言，只要算法中不存在循環(huán)語句，其時(shí)間復(fù)雜度就是Ο(1)弟蚀。其中Ο(log2n)义钉、Ο(n)规肴、 Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項(xiàng)式時(shí)間删壮，而Ο(2n)和Ο(n!)稱為指數(shù)時(shí)間兑牡。計(jì)算機(jī)科學(xué)家普遍認(rèn)為前者（即多項(xiàng)式時(shí)間復(fù)雜度的算法）是有效算法发绢，把這類問題稱為P（Polynomial,多項(xiàng)式）類問題，而把后者（即指數(shù)時(shí)間復(fù)雜度的算法）稱為NP（Non-Deterministic Polynomial, 非確定多項(xiàng)式）問題经柴。
一般來說多項(xiàng)式級(jí)的復(fù)雜度是可以接受的墩朦，很多問題都有多項(xiàng)式級(jí)的解——也就是說氓涣，這樣的問題，對(duì)于一個(gè)規(guī)模是n的輸入引润，在n^k的時(shí)間內(nèi)得到結(jié)果痒玩，稱為P問題。有些問題要復(fù)雜些奴曙，沒有多項(xiàng)式時(shí)間的解洽糟，但是可以在多項(xiàng)式時(shí)間里驗(yàn)證某個(gè)猜測(cè)是不是正確堕战。比如問4294967297是不是質(zhì)數(shù)？如果要直接入手的話浇雹，那么要把小于4294967297的平方根的所有素?cái)?shù)都拿出來屿讽，看看能不能整除伐谈。還好歐拉告訴我們，這個(gè)數(shù)等于641和6700417的乘積抠蚣，不是素?cái)?shù)履澳，很好驗(yàn)證的，順便麻煩轉(zhuǎn)告費(fèi)馬他的猜想不成立吻谋。大數(shù)分解现横、Hamilton回路之類的問題，都是可以多項(xiàng)式時(shí)間內(nèi)驗(yàn)證一個(gè)“解”是否正確骇两，這類問題叫做NP問題姜盈。
計(jì)算時(shí)間復(fù)雜度的分析法則
- 對(duì)于一些簡(jiǎn)單的輸入輸出語句或賦值語句,近似認(rèn)為需要O(1)時(shí)間
- 對(duì)于順序結(jié)構(gòu),需要依次執(zhí)行一系列語句所用的時(shí)間可采用大O下"求和法則"
求和法則:
是指若算法的2個(gè)部分時(shí)間復(fù)雜度分別為 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))
- 對(duì)于選擇結(jié)構(gòu),如if語句,它的主要時(shí)間耗費(fèi)是在執(zhí)行then字句或else字句所用的時(shí)間,需注意的是檢驗(yàn)條件也需要O(1)時(shí)間
- 對(duì)于循環(huán)結(jié)構(gòu),循環(huán)語句的運(yùn)行時(shí)間主要體現(xiàn)在多次迭代中執(zhí)行循環(huán)體以及檢驗(yàn)循環(huán)條件的時(shí)間耗費(fèi),一般可用大O下"乘法法則"
乘法法則:
是指若算法的2個(gè)部分時(shí)間復(fù)雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),
則 T1*T2=O(f(n)*g(n))
- 對(duì)于復(fù)雜的算法,可以將它分成幾個(gè)容易估算的部分,然后利用求和法則和乘法法則技術(shù)整個(gè)算法的時(shí)間復(fù)雜度
另外還有以下2個(gè)運(yùn)算法則:
(1) 若g(n)=O(f(n)),則O(f(n))+ O(g(n))= O(f(n))栋操；
(2) O(Cf(n)) = O(f(n)),其中C是一個(gè)正常數(shù)
常見時(shí)間復(fù)雜度示例：
- O(1)
Temp=i; i=j; j=temp;
解：
以上三條單個(gè)語句的頻度均為1饱亮，該程序段的執(zhí)行時(shí)間是一個(gè)與問題規(guī)模n無關(guān)的常數(shù)。
算法的時(shí)間復(fù)雜度為常數(shù)階剔宪，記作T(n)=O(1)壹无。
注意：如果算法的執(zhí)行時(shí)間不隨著問題規(guī)模n的增加而增長(zhǎng)斗锭，即使算法中有上千條語句，其執(zhí)行時(shí)間也不過是一個(gè)較大的常數(shù)帮毁。
此類算法的時(shí)間復(fù)雜度是O(1)烈疚。
- O(n2)
- 示例1
sum=0聪轿； （一次）
for(int i = 1; i <= n; i++) （n+1次）
for(int j = 1; j <= n; j++) （n2次）
sum++； （n2次）
解：
因?yàn)棣?2n2+n+1)=n2（Θ即：去低階項(xiàng)灯抛，去掉常數(shù)項(xiàng)对嚼，去掉高階項(xiàng)的常參得到）
所以T(n)= =O(n2)；
- 示例2
for (int i = 1; i < n; i++)
{
y = y + 1; ①
for (int j = 0; j <= (2 * n); j++)
x++; ②
}
解：
語句1的頻度是n-1
語句2的頻度是(n-1)*(2n+1)=2n2-n-1
f(n)=2n2-n-1+(n-1)=2n2-2；
又Θ(2n2-2)=n2
該程序的時(shí)間復(fù)雜度T(n)=O(n2).
PS: 一般情況下磨确，對(duì)步進(jìn)循環(huán)語句只需考慮循環(huán)體中語句的執(zhí)行次數(shù)声邦，忽略該語句中步長(zhǎng)加1亥曹、終值判別、控制轉(zhuǎn)移等成分骗炉，當(dāng)有若干個(gè)循環(huán)語句時(shí)蛇受，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的兢仰。
- O(n)
int s;
int a = 0;
int b = 1; ①
for (int i = 1; i <= n; i++) ②
{
s = a + b; ③
b = a; ∏嶙ā④
a = s; 〔於住⑤
}
解：
語句1的頻度：2,
語句2的頻度： n,
語句3的頻度： n-1,
語句4的頻度：n-1,
語句5的頻度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).
- O(log2n)
int i = 1; ①
while (i <= n)
i = i * 2; ②
解：
語句1的頻度是1,
設(shè)語句2的頻度是f(n), 則：2^f(n)<=n;f(n)<=log2n
取最大值f(n)=log2n,
T(n)=O(log2n )
- O(n3)
for(int i = 0; i < n; i++)
{
for(int j = 0; j < i; j++)
{
for(int k = 0; k < j; k++)
x = x + 2;
}
}
解：
當(dāng)i=m, j=k的時(shí)候,內(nèi)層循環(huán)的次數(shù)為k當(dāng)i=m時(shí), j 可以取 0,1,...,m-1 ,
所以這里最內(nèi)循環(huán)共進(jìn)行了0+1+...+m-1=(m-1)m/2次所以,i從0取到n,
則循環(huán)共進(jìn)行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以時(shí)間復(fù)雜度為O(n3).
常用算法的時(shí)間復(fù)雜度
- O(1): 表示算法的運(yùn)行時(shí)間為常量
O(n): 表示該算法是線性算法
O(㏒2n): 二分查找算法
O(n2): 對(duì)數(shù)組進(jìn)行排序的各種簡(jiǎn)單算法洽议，例如直接插入排序的算法绞铃。
O(n3): 做兩個(gè)n階矩陣的乘法運(yùn)算
O(2n): 求具有n個(gè)元素集合的所有子集的算法
O(n!): 求具有N個(gè)元素的全排列的算法 - 優(yōu)<---------------------------<劣
O(1)<O(㏒2n)<O(n)<O(n2)<O(2n)
時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)階O(1)、對(duì)數(shù)階O(log2n)荚坞、線性階O(n)颓影、線性對(duì)數(shù)階O(nlog2n)、平方階O(n2)碎浇、立方階O(n3)璃俗、……k次方階O(nk)城豁、指數(shù)階O(2n)。
空間復(fù)雜度
- 類似于時(shí)間復(fù)雜度的討論雳旅，一個(gè)算法的空間復(fù)雜度(Space Complexity)S(n)定義為該算法所耗費(fèi)的存儲(chǔ)空間攒盈，它也是問題規(guī)模n的函數(shù)哎榴。漸近空間復(fù)雜度也常常簡(jiǎn)稱為空間復(fù)雜度。
- 空間復(fù)雜度(Space Complexity)是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度偷遗。一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間氏豌，包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間热凹，算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間這三個(gè)方面般妙。算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間是由要解決的問題決定的，是通過參數(shù)表由調(diào)用函數(shù)傳遞而來的鲜锚，它不隨本算法的不同而改變。存儲(chǔ)算法本身所占用的存儲(chǔ)空間與算法書寫的長(zhǎng)短成正比旺隙，要壓縮這方面的存儲(chǔ)空間蔬捷，就必須編寫出較短的算法榔袋。算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間隨算法的不同而異，有的算法只需要占用少量的臨時(shí)工作單元妥粟，而且不隨問題規(guī)模的大小而改變，我們稱這種算法是“就地/"進(jìn)行的备恤，是節(jié)省存儲(chǔ)的算法露泊，如這一節(jié)介紹過的幾個(gè)算法都是如此；有的算法需要占用的臨時(shí)工作單元數(shù)與解決問題的規(guī)模n有關(guān)侣姆，它隨著n的增大而增大沉噩，當(dāng)n較大時(shí)川蒙，將占用較多的存儲(chǔ)單元，快速排序和歸并排序算法就屬于這種情況昼牛。
- 如當(dāng)一個(gè)算法的空間復(fù)雜度為一個(gè)常量贰健，即不隨被處理數(shù)據(jù)量n的大小而改變時(shí)恬汁，可表示為O(1)；當(dāng)一個(gè)算法的空間復(fù)雜度與以2為底的n的對(duì)數(shù)成正比時(shí)悬垃，可表示為0(10g2n)尝蠕；當(dāng)一個(gè)算法的空I司復(fù)雜度與n成線性比例關(guān)系時(shí)，可表示為0(n).若形參為數(shù)組廊佩，則只需要為它分配一個(gè)存儲(chǔ)由實(shí)參傳送來的一個(gè)地址指針的空間靖榕，即一個(gè)機(jī)器字長(zhǎng)空間茁计；若形參為引用方式，則也只需要為其分配存儲(chǔ)一個(gè)地址的空間践剂，用它來存儲(chǔ)對(duì)應(yīng)實(shí)參變量的地址逊脯，以便由系統(tǒng)自動(dòng)引用實(shí)參變量竣贪。
常用時(shí)間復(fù)雜度的記法
- 訪問數(shù)組中的元素是常數(shù)時(shí)間操作演怎，或說O(1)操作。
- 一個(gè)算法如 果能在每個(gè)步驟去掉一半數(shù)據(jù)元素汗捡，如二分檢索畏纲，通常它就取 O(logn)時(shí)間盗胀。
- 用strcmp比較兩個(gè)具有n個(gè)字符的串需要O(n)時(shí)間 。
- 常規(guī)的矩陣乘算法是O(n^3)女阀，因?yàn)樗愠雒總€(gè)元素都需要將n對(duì) 元素相乘并加到一起浸策，所有元素的個(gè)數(shù)是n^2。
- 指數(shù)時(shí)間算法通常來源于需要求出所有可能結(jié)果惫确。例如改化，n個(gè)元 素的集合共有2n個(gè)子集,所以要求出所有子集的算法將是O(2n)的 枉昏。指數(shù)算法一般說來是太復(fù)雜了兄裂，除非n的值非常小，因?yàn)樘溉觯?這個(gè)問題中增加一個(gè)元素就導(dǎo)致運(yùn)行時(shí)間加倍港华。不幸的是午衰，確實(shí)有許多問題 (如著名 的“巡回售貨員問題” )臊岸，到目前為止找到的算法都是指數(shù)的尊流。如果我們真的遇到這種情況， 通常應(yīng)該用尋找近似最佳結(jié)果的算法替代之逻住。
參考
以上瞎访！
