時間復(fù)雜度和空間復(fù)雜度

1、算法的時間復(fù)雜度和空間復(fù)雜度合稱為算法的復(fù)雜度。1.時間復(fù)雜度（1）時間頻度 一個算法執(zhí)行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度。記為T(n)。（2）時間復(fù)雜度 在剛才提到的時間頻度中，n稱為問題的規(guī)模，當(dāng)n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現(xiàn)什么規(guī)律。為此，我們引入時間復(fù)

2、雜度概念。 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時，T（n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=(f(n),稱(f(n) 為算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。     時間頻度不同，但時間復(fù)雜度可能相同。如：T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復(fù)雜度相同，都為O(n2)。    按數(shù)量級遞增排列，常見的時間復(fù)雜度有：常數(shù)階O(1),對數(shù)階O(log2n)

3、,線性階O(n), 線性對數(shù)階O(nlog2n),平方階O(n2)，立方階O(n3),.， k次方階O(nk),指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。 （3）最壞時間復(fù)雜度和平均時間復(fù)雜度 最壞情況下的時間復(fù)雜度稱最壞時間復(fù)雜度。一般不特別說明，討論的時間復(fù)雜度均是最壞情況下的時間復(fù)雜度。 這樣做的原因是：最壞情況下的時間復(fù)雜度是算法在任何輸入實例上運行時間的上界，這就保證了算法的運行時間不會比任何更長。     在最壞情況下的時間復(fù)雜度為T(n)=0(n)，它表示對于任何輸入實例,該算法的運行

4、時間不可能大于0(n)。 平均時間復(fù)雜度是指所有可能的輸入實例均以等概率出現(xiàn)的情況下，算法的期望運行時間。    指數(shù)階0(2n)，顯然，時間復(fù)雜度為指數(shù)階0(2n)的算法效率極低，當(dāng)n值稍大時就無法應(yīng)用。（4）求時間復(fù)雜度【1】如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句，其執(zhí)行時間也不過是一個較大的常數(shù)。此類算法的時間復(fù)雜度是O(1)。x=91; y=100;while(y>0) if(x>100) x=x-10;y-; else x+;解答： T(n)=O(1)，這個程序看起來有點嚇人，總共循環(huán)運行了1100次，但是我們看到n沒有

5、?沒。這段程序的運行是和n無關(guān)的，就算它再循環(huán)一萬年，我們也不管他，只是一個常數(shù)階的函數(shù)【2】當(dāng)有若干個循環(huán)語句時，算法的時間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的。 x=1; for(i=1;i<=n;i+)         for(j=1;j<=i;j+)           for(k=1;k<=j;k+)               x

6、+; 該程序段中頻度最大的語句是(5)，內(nèi)循環(huán)的執(zhí)行次數(shù)雖然與問題規(guī)模n沒有直接關(guān)系，但是卻與外層循環(huán)的變量取值有關(guān)，而最外層循環(huán)的次數(shù)直接與n有關(guān)，因此可以從內(nèi)層循環(huán)向外層分析語句(5)的執(zhí)行次數(shù)：  則該程序段的時間復(fù)雜度為T(n)=O(n3/6+低次項)=O(n3)【3】算法的時間復(fù)雜度不僅僅依賴于問題的規(guī)模，還與輸入實例的初始狀態(tài)有關(guān)。在數(shù)值A(chǔ)0.n-1中查找給定值K的算法大致如下：   i=n-1;            while(i>=0&&(Ai!

7、=k)             i-;        return i;        此算法中的語句(3)的頻度不僅與問題規(guī)模n有關(guān)，還與輸入實例中A的各元素取值及K的取值有關(guān): 若A中沒有與K相等的元素，則語句(3)的頻度f(n)=n； 若A的最后一個元素等于K,則語句(3)的頻度f(n)是常數(shù)0。（5）時間復(fù)雜度評價性能 有兩個算法A1和A2求解同一問題，時間復(fù)雜度分別是T1(n)

8、=100n2，T2(n)=5n3。（1）當(dāng)輸入量n20時，有T1(n)T2(n)，后者花費的時間較少。（2）隨著問題規(guī)模n的增大，兩個算法的時間開銷之比5n3/100n2=n/20亦隨著增大。即當(dāng)問題規(guī)模較大時，算法A1比算法A2要有效地多。它們的漸近時間復(fù)雜度O(n2)和O(n3)從宏觀上評價了這兩個算法在時間方面的質(zhì)量。在算法分析時，往往對算法的時間復(fù)雜度和漸近時間復(fù)雜度不予區(qū)分，而經(jīng)常是將漸近時間復(fù)雜度T(n)=O(f(n)簡稱為時間復(fù)雜度，其中的f(n)一般是算法中頻度最大的語句頻度。2.空間復(fù)雜度一個程序的空間復(fù)雜度是指運行完一個程序所需內(nèi)存的大小。利用程序的空間復(fù)雜度，可以對程序的

9、運行所需要的內(nèi)存多少有個預(yù)先估計。一個程序執(zhí)行時除了需要存儲空間和存儲本身所使用的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需要一些對數(shù)據(jù)進(jìn)行操作的工作單元和存儲一些為現(xiàn)實計算所需信息的輔助空間。程序執(zhí)行時所需存儲空間包括以下兩部分。（1）固定部分。這部分空間的大小與輸入/輸出的數(shù)據(jù)的個數(shù)多少、數(shù)值無關(guān)。主要包括指令空間（即代碼空間）、數(shù)據(jù)空間（常量、簡單變量）等所占的空間。這部分屬于靜態(tài)空間。（2）可變空間，這部分空間的主要包括動態(tài)分配的空間，以及遞歸棧所需的空間等。這部分的空間大小與算法有關(guān)。一個算法所需的存儲空間用f(n)表示。S(n)=O(f(n)其中n為問題的規(guī)模，S(n)表示空間復(fù)雜度。算法

10、的時間復(fù)雜度和空間復(fù)雜度-總結(jié)        通常，對于一個給定的算法，我們要做 兩項分析。第一是從數(shù)學(xué)上證明算法的正確性，這一步主要用到形式化證明的方法及相關(guān)推理模式，如循環(huán)不變式、數(shù)學(xué)歸納法等。而在證明算法是正確的基礎(chǔ)上，第二部就是分析算法的時間復(fù)雜度。算法的時間復(fù)雜度反映了程序執(zhí)行時間隨輸入規(guī)模增長而增長的量級，在很大程度上能很好反映出算法的優(yōu)劣與否。因此，作為程序員，掌握基本的算法時間復(fù)雜度分析方法是很有必要的。       算法執(zhí)行時間需通過依據(jù)該算法編制

11、的程序在計算機上運行時所消耗的時間來度量。而度量一個程序的執(zhí)行時間通常有兩種方法。一、事后統(tǒng)計的方法        這種方法可行，但不是一個好的方法。該方法有兩個缺陷：一是要想對設(shè)計的算法的運行性能進(jìn)行評測，必須先依據(jù)算法編制相應(yīng)的程序并實際運行；二是所得時間的統(tǒng)計量依賴于計算機的硬件、軟件等環(huán)境因素，有時容易掩蓋算法本身的優(yōu)勢。二、事前分析估算的方法        因事后統(tǒng)計方法更多的依賴于計算機的硬件、軟件等環(huán)境因素，有時容易掩蓋算法本身的優(yōu)

12、劣。因此人們常常采用事前分析估算的方法。在編寫程序前，依據(jù)統(tǒng)計方法對算法進(jìn)行估算。一個用高級語言編寫的程序在計算機上運行時所消耗的時間取決于下列因素：      (1). 算法采用的策略、方法；(2). 編譯產(chǎn)生的代碼質(zhì)量；(3). 問題的輸入規(guī)模；(4).  機器執(zhí)行指令的速度。     一個算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)3種）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的，則算法時間取決于兩者的綜合效果。為了便于比較同一個問題的不同算法

13、，通常的做法是，從算法中選取一種對于所研究的問題（或算法類型）來說是基本操作的原操作，以該基本操作的重復(fù)執(zhí)行的次數(shù)作為算法的時間量度。1、時間復(fù)雜度 （1）時間頻度 一個算法執(zhí)行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度。記為T(n)。（2）時間復(fù)雜度 在剛才提到的時間頻度中，n稱為問題的規(guī)模，當(dāng)n不

14、斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現(xiàn)什么規(guī)律。為此，我們引入時間復(fù)雜度概念。 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=(f(n),稱(f(n) 為算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。       另外，上面公式中用到的 Landau符號其實是由德國數(shù)論學(xué)家保羅·巴赫曼（Paul Bachm

15、ann）在其1892年的著作解析數(shù)論首先引入，由另一位德國數(shù)論學(xué)家艾德蒙·朗道（Edmund Landau）推廣。Landau符號的作用在于用簡單的函數(shù)來描述復(fù)雜函數(shù)行為，給出一個上或下（確）界。在計算算法復(fù)雜度時一般只用到大O符號，Landau符號體系中的小o符號、符號等等比較不常用。這里的O，最初是用大寫希臘字母，但現(xiàn)在都用大寫英語字母O；小o符號也是用小寫英語字母o，符號則維持大寫希臘字母。        T (n) = (f (n) 表示存在一個常數(shù)C，使得在當(dāng)n趨于正無窮時總有 T (

16、n) C * f(n)。簡單來說，就是T(n)在n趨于正無窮時最大也就跟f(n)差不多大。也就是說當(dāng)n趨于正無窮時T (n)的上界是C * f(n)。其雖然對f(n)沒有規(guī)定，但是一般都是取盡可能簡單的函數(shù)。例如，O(2n2+n +1) = O (3n2+n+3) = O (7n2 + n) = O ( n2 ) ，一般都只用O(n2)表示就可以了。注意到大O符號里隱藏著一個常數(shù)C，所以f(n)里一般不加系數(shù)。如果把T(n)當(dāng)做一棵樹，那么O(f(n)所表達(dá)的就是樹干，只關(guān)心其中的主干，其他的細(xì)枝末節(jié)全都拋棄不管。  

17、60;     在各種不同算法中，若算法中語句執(zhí)行次數(shù)為一個常數(shù)，則時間復(fù)雜度為O(1),另外，在時間頻度不相同時，時間復(fù)雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復(fù)雜度相同，都為O(n2)。 按數(shù)量級遞增排列，常見的時間復(fù)雜度有：常數(shù)階O(1),對數(shù)階O(log2n),線性階O(n), 線性對數(shù)階O(nlog2n),平方階O(n2)，立方階O(n3),.， k次方階O(nk),指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。  

18、60;從圖中可見，我們應(yīng)該盡可能選用多項式階O(nk)的算法，而不希望用指數(shù)階的算法。      常見的算法時間復(fù)雜度由小到大依次為：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)(n!)       一般情況下，對一個問題（或一類算法）只需選擇一種基本操作來討論算法的時間復(fù)雜度即可，有時也需要同時考慮幾種基本操作，甚至可以對不同的操作賦予不同的權(quán)值，以反映執(zhí)行不同操作所需的相對時間，這種做法便于綜合比較解決同一問題的兩種完全不同的算法。（3）求解算法的時間復(fù)雜度的

19、具體步驟是： 找出算法中的基本語句；算法中執(zhí)行次數(shù)最多的那條語句就是基本語句，通常是最內(nèi)層循環(huán)的循環(huán)體。 計算基本語句的執(zhí)行次數(shù)的數(shù)量級；只需計算基本語句執(zhí)行次數(shù)的數(shù)量級，這就意味著只要保證基本語句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡化算法分析，并且使注意力集中在最重要的一點上：增長率。 用大記號表示算法的時間性能。將基本語句執(zhí)行次數(shù)的數(shù)量級放入大記號中。如果算法中包含嵌套的循環(huán)，則基本語句通常是最內(nèi)層的循環(huán)體，如果算法中包含并列的循環(huán)，則將并列循環(huán)的時間復(fù)雜度相加。例如：java view plain copy1. for&#

20、160;(i=1; i<=n; i+)  2.        x+;  3. for (i=1; i<=n; i+)  4.     for (j=1; j<=n; j+)  5.           x+;&#

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

22、問題。        一般來說多項式級的復(fù)雜度是可以接受的，很多問題都有多項式級的解也就是說，這樣的問題，對于一個規(guī)模是n的輸入，在nk的時間內(nèi)得到結(jié)果，稱為P問題。有些問題要復(fù)雜些，沒有多項式時間的解，但是可以在多項式時間里驗證某個猜測是不是正確。比如問4294967297是不是質(zhì)數(shù)？如果要直接入手的話，那么要把小于4294967297的平方根的所有素數(shù)都拿出來，看看能不能整除。還好歐拉告訴我們，這個數(shù)等于641和6700417的乘積，不是素數(shù)，很好驗證的，順便麻煩轉(zhuǎn)告費馬他的猜想不成立。大數(shù)分解、Hamilton回路之類

23、的問題，都是可以多項式時間內(nèi)驗證一個“解”是否正確，這類問題叫做NP問題。（4）在計算算法時間復(fù)雜度時有以下幾個簡單的程序分析法則:(1).對于一些簡單的輸入輸出語句或賦值語句,近似認(rèn)為需要O(1)時間(2).對于順序結(jié)構(gòu),需要依次執(zhí)行一系列語句所用的時間可采用大O下"求和法則"求和法則:是指若算法的2個部分時間復(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)(3).對于選擇結(jié)構(gòu)

24、,如if語句,它的主要時間耗費是在執(zhí)行then字句或else字句所用的時間,需注意的是檢驗條件也需要O(1)時間(4).對于循環(huán)結(jié)構(gòu),循環(huán)語句的運行時間主要體現(xiàn)在多次迭代中執(zhí)行循環(huán)體以及檢驗循環(huán)條件的時間耗費,一般可用大O下"乘法法則"乘法法則: 是指若算法的2個部分時間復(fù)雜度分別為 T1(n)=O(f(n)和 T2(n)=O(g(n),則 T1*T2=O(f(n)*g(n)(5).對于復(fù)雜的算法,可以將它分成幾個容易估算的部分,然后利用求和法則和乘法法則技術(shù)整個算法的時間復(fù)雜度另外還有以下2個運算法則:(1) 若g(n)=O(f(n),則O(f(n)+ O(g(n)= O

25、(f(n)；(2) O(Cf(n) = O(f(n),其中C是一個正常數(shù) （5）下面分別對幾個常見的時間復(fù)雜度進(jìn)行示例說明：(1)、O(1)        Temp=i; i=j; j=temp;                    以上三條單個語句的頻度均為1，該程序段的執(zhí)行時間是一個與問題規(guī)模n無關(guān)的常數(shù)。算法的

26、時間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。注意：如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句，其執(zhí)行時間也不過是一個較大的常數(shù)。此類算法的時間復(fù)雜度是O(1)。(2)、O(n2)2.1. 交換i和j的內(nèi)容java view plain copy1. sum=0；                 （一次）  2. for(i=1;i<=n;i+) 

27、;    （n+1次）  3.    for(j=1;j<=n;j+) （n2次）  4.     sum+；            （n2次）  解：因為(2n2+n+1)=n2（即：去低階項，去掉常數(shù)項，去掉高階項的常參得到），所以T(n)= =O(n2)；2.2.  

28、 java view plain copy1. for (i=1;i<n;i+)  2.     3.      y=y+1;              4.      for (j=0;j<=(2*n);j+)  &

29、#160;   5.         x+;                 6.              解： 語句1的頻度是n-1    

30、60;     語句2的頻度是(n-1)*(2n+1)=2n2-n-1          f(n)=2n2-n-1+(n-1)=2n2-2；        又(2n2-2)=n2          該程序的時間復(fù)雜度T(n)=O(n2).  一般情況下，對步進(jìn)循環(huán)語句只需考慮循環(huán)體中語句的

31、執(zhí)行次數(shù)，忽略該語句中步長加1、終值判別、控制轉(zhuǎn)移等成分，當(dāng)有若干個循環(huán)語句時，算法的時間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的。     (3)、O(n)                              

32、0;                               java view plain copy1. a=0;  2.   b=1;       &#

33、160;                3.   for (i=1;i<=n;i+)   4.       5.      s=a+b;  6.      b=a;  

34、60; 7.      a=s;  8.     解： 語句1的頻度：2,                   語句2的頻度： n,              

35、    語句3的頻度： n-1,                  語句4的頻度：n-1,              語句5的頻度：n-1,           

36、;                                 T(n)=2+n+3(n-1)=4n-1=O(n).(4)、O(log2n)java view plain copy1. i=1;     &

37、#160; 2. hile (i<=n)  3.   i=i*2;   解： 語句1的頻度是1,            設(shè)語句2的頻度是f(n),   則：2f(n)<=n;f(n)<=log2n              取最大值

38、f(n)=log2n,          T(n)=O(log2n )(5)、O(n3) java view plain copy1. for(i=0;i<n;i+)  2.        3.       for(j=0;j<i;j+)    4.         5.          for(k=0;k<j;k+)  6.             x=x+2;    7.