算法的時間復(fù)雜度
Edit:
用了代碼高亮腳本以后超過字?jǐn)?shù)上限
高亮后的代碼會放在回復(fù)里……
========
首先謝謝小年給開了日志~~
然后抄送某個多線程反而比單線程慢的小破孩。。。
看了下發(fā)現(xiàn)代碼縮進(jìn)神馬的都不見了。。。。納斯達(dá)克老師新的腳本里貌似沒有更新代碼支持部分呢……
最后，第一次寫科普文，求各種批評指點，尤其是在非技術(shù)的方面。。
謝謝啦~~
=================
在信息化的時代里每個人都應(yīng)該懂一點編程。重復(fù)性的機(jī)械勞動，都應(yīng)該交給機(jī)器去做，從而把人的精力放在更有挑戰(zhàn)性的任務(wù)上。寫代碼第一個要避免的就是syntex error和類似這里（
http://www.guokr.com/post/65643/）所寫非所想的錯誤；第二個就是要注意算法的復(fù)雜度。一個程序沒有bug，但是因為算法不夠優(yōu)化，最后要很長時間才能得出結(jié)果，發(fā)生這種事呢，大家都不想的。這里就從斐波那契數(shù)列入手，來講講算法的時間復(fù)雜度。
0. 準(zhǔn)備工作： Landau符號
Landau符號其實是由德國數(shù)論學(xué)家保羅·巴赫曼（Paul Bachmann）在其1892年的著作《解析數(shù)論》首先引入，由另一位德國數(shù)論學(xué)家艾德蒙·朗道（Edmund Landau）推廣。Landau符號的作用在于用簡單的函數(shù)來描述復(fù)雜函數(shù)行為，給出一個上或下（確）界。在計算算法復(fù)雜度時一般只用到大O符號，Landau符號體系中的小o符號、Θ符號等等比較不常用。這里的O，最初是用大寫希臘字母，但現(xiàn)在都用大寫英語字母O；小o符號也是用小寫英語字母o，Θ符號則維持大寫希臘字母Θ。
f (n) = Ο(g (n)) 表示存在一個常數(shù)C，使得在當(dāng)n趨于正無窮時總有 f (n) ≤ C * g(n)。簡單來說，就是f(n)在n趨于正無窮時最大也就跟g(n)差不多大。雖然對g(n)沒有規(guī)定，但是一般都是取盡可能簡單的函數(shù)。例如，O(2n^2+n +1) = O (3n^2+n+3) = O (7n^2 + n) = O ( n^2 ) ，一般都只用O(n^2)表示就可以了。注意到大O符號里隱藏著一個常數(shù)C，所以g(n)里一般不加系數(shù)。如果把f(n)當(dāng)做一棵樹，那么O(g(n))所表達(dá)的就是樹干，只關(guān)心其中的主干，其他的細(xì)枝末節(jié)全都拋棄不管。
在時間復(fù)雜度計算中常見的級別有O(1)， O(log n) ， O(n), O(n * log n) , O(n^k)， O(a^n), O(n!)，其大小逐級上升：
注意到所有的對數(shù)只不過相差一個常數(shù)，所以這里都用了常用對數(shù)。另外一般程序只處理32位的數(shù)據(jù)，因此最大整數(shù)是2^32-1，大約等于10^9。因此log n可以認(rèn)為是近似等于10的常數(shù)，也就是說O(log n)的近似等于O(1)，O(n * log n)近似等于O(n)，這點也在上表中有所反應(yīng)。
全國有10^9個人，一個人大約有10^14個細(xì)胞，一摩爾基本粒子中有10^24個（大致相當(dāng)于全國人民身上的細(xì)胞總數(shù)），宇宙中大概有10^80個基本粒子，所以上表中的某些數(shù)字，你懂的……
1 算法的時間復(fù)雜度
好了，了解了Landou或者叫大O符號，我們就可以來討論算法的時間復(fù)雜度了。一個算法，對于一個規(guī)模是n的輸入，需要T(n)的時間進(jìn)行運算。T(n)的具體值，一方面取決于算法，另一方面和計算用的工具也有關(guān)。但我們關(guān)心的是，當(dāng)n擴(kuò)大100倍以后，T(n)是幾乎不變，還是擴(kuò)大了100倍、10000倍或者怎樣。也就是說，我們關(guān)心的是規(guī)模擴(kuò)大后，運算時間增長得有多快，是一個相對的結(jié)果，而不是絕對結(jié)果。
建立一個空列表，需要的時間總是固定的，就是O(1)；如果有一句for或者while的語句，把同一行代碼運算了n次，那么就是O(n)級的復(fù)雜度；如果for下面還有for，各自要算n次，那么就是n^2的復(fù)雜度，以此類推。
復(fù)雜度舉例：
* O(1) 常數(shù)級復(fù)雜度，也就是說程序運行的時間與需要處理的數(shù)據(jù)大小無關(guān)。通常把比較大小、加減乘除等簡單的運算都當(dāng)做常數(shù)級復(fù)雜度。 值得注意的是，在處理大數(shù)（二進(jìn)制下數(shù)據(jù)長度超過32位或者十進(jìn)制下超過8位）時，將加減乘除等運算當(dāng)做常數(shù)復(fù)雜度不再適用。
* O(log n) 將一個10進(jìn)制整數(shù)轉(zhuǎn)化為2進(jìn)制整數(shù)
* O(n)：判斷一個元素是否屬于一個大小為n的集合/列表；找出n個數(shù)中的最大值；
* O(n * log n) 快速排序法
* O(n^2) 最直白的兩兩比較然后排序方法，需要n*(n-1)/2次比較，所以是O(n^2)級。
* O(2^n) 列出所有長度為n的0,1字符串之類的窮舉計算
* O(n!) 列出n個元素的全排列之類的窮舉計算
一般來說多項式級的復(fù)雜度是可以接受的，很多問題都有多項式級的解——也就是說，這樣的問題，對于一個規(guī)模是n的輸入，在n^k的時間內(nèi)得到結(jié)果，稱為P問題。有些問題要復(fù)雜些，沒有多項式時間的解，但是可以在多項式時間里驗證某個猜測是不是正確。比如問4294967297是不是質(zhì)數(shù)？如果要直接入手的話，那么要把小于4294967297的平方根的所有素數(shù)都拿出來，看看能不能整除。還好歐拉告訴我們，這個數(shù)等于641和6700417的乘積，不是素數(shù)，很好驗證的，順便麻煩轉(zhuǎn)告費馬他的猜想不成立。大數(shù)分解、Hamilton回路之類的問題，都是可以多項式時間內(nèi)驗證一個“解”是否正確，這類問題叫做NP問題。（據(jù)信程序猿找妹子也是一個NP問題。。）
P問題顯然都是NP問題——既然你能在多項式時間里得到答案，那么只要比較一下答案和猜測是不是一樣就可以驗證一個解。反過來，多數(shù)人相信，NP問題不都是P問題。幾個月前看到一篇論文說NP不等于P，但沒有看到后續(xù)報道，也讀不懂原文，攤手……如果NP問題都是P問題，那么大數(shù)分解不再是難題，從而基于大數(shù)分解的RSA加密系統(tǒng)頓時崩潰；同樣md5算法也不再有效，甚至現(xiàn)在所有的多項式復(fù)雜度的加密算法都沒用了——不過這樣一來程序猿也可以方便地找到妹子了，說起來并不是一無是處嘛……
2 斐波那契數(shù)列
早在1150年印度科學(xué)家Gopala就研究過斐波那契數(shù)列，但正如Landau搶走了Landau符號的命名一樣，斐波那契也獲得了不屬于他的數(shù)列的冠名權(quán)。斐波那契數(shù)列是和兔子緊緊聯(lián)系在一起的。 斐波那契的兔子是這樣的一個模型：一開始有一對小兔子。小兔子需要一個月以后才能長成大兔子從而擁有生育能力；所有擁有生育能力的大兔子每個月都會生一對小兔子。所有的兔子都長生不老，問第n個月一共有多少兔子呢？
維基百科詞條中有這樣一張直觀的圖：
讓我們列一個表來看看每個月大兔子小兔子各有多少只：
從表中我們可以找到這樣的規(guī)律：
F(n)=F(n-1)+F(n-2)
這就是斐波那契數(shù)列的遞推公式，可以用數(shù)學(xué)歸納法證明。
利用一些數(shù)學(xué)工具我們可以得到斐波那契數(shù)列的通項公式：
其中小括號里的兩個數(shù)是方程 x^2-x-1=0的解，跟著名的黃金分割比有密切的關(guān)系。
用上面的Landau符號，有F(n) = O(^n)，其中是黃金分割比：
所以說，兔子的增長速度還是非常快的……
斐波那契數(shù)列還可以通過下面的矩陣乘方來實現(xiàn)，這點會在后面的算法中用到。對矩陣不熟悉的讀者，暫時可以認(rèn)為這里2階矩陣的乘法是兩組4元數(shù)組之間的運算，結(jié)果仍然是一組4元數(shù)組；對于相同的矩陣（4元數(shù)組），這個運算滿足交換律和結(jié)合律。
3 三種程序計算斐波那契數(shù)列第n項
第一種算法，too simple, sometimes naif，直接從遞推公式下手：
def fibo_1(n):
'''
簡單遞歸方法求斐波那契數(shù)列第n項。
輸入變量n應(yīng)當(dāng)為正整數(shù)。(對非法輸入沒有警告）
'''
if n < 3:
res=1 #設(shè)定初始狀態(tài)：F(1)=F(2)=1
else:
res=fibo_1(n-1)+fibo_1(n-2) #遞歸公式
return res
這樣計算的復(fù)雜度是怎樣能？讓我們看看遞歸次數(shù)：
可以看到計算F(n)，需要的遞歸次數(shù)是F(n-2)。
指數(shù)級的復(fù)雜度啊……
不行不行，我要提高自身修養(yǎng)，看看第二個算法：
def fibo_2(n):
'''
通過遞歸方法求斐波那契數(shù)列第n項
變量n應(yīng)當(dāng)為正整數(shù)。（對非法輸入沒有警告）
記錄最后兩項計算結(jié)果
'''
a=1
b=1 #設(shè)定初始狀態(tài)，a=F(1),b=F(2)
for i in range(2,n):
a,b=a+b,a # 由數(shù)學(xué)歸納法易得第i步中a=F(i),b=F(i-1)
return a #循環(huán)結(jié)束時i=n，a=F(n)
分析：這次好多了，for語句，循環(huán)n-2次，O(n)級的復(fù)雜度。
最后來個利用矩陣乘方的算法，只需要O(log n)的復(fù)雜度，可以跟美國的那個誰談笑風(fēng)生了：
def fibo_3(n):
'''
將求斐波那契數(shù)列轉(zhuǎn)化為求2階矩陣n次冪問題。
'''
def prod(m1,m2):
'''
兩個矩陣的乘積
'''
a1,b1,c1,d1=m1
a2,b2,c2,d2=m2
return (a1*a2+b1*c2,a1*b2+c1*d2,a2*c1+c2*d1,b2*c1+d1*d2)
def pui(m,n):
'''
求一個矩陣m的n次冪。
如n=2k+1，則m^n=(m^k)^2*m;
如n=2k，則m^n=(m^k)^2。
'''
if n == 1:
return m
else:
res=pui(m,n//2) #上述的k=n//2，//表示帶余除法的商，例如 5//2 = 2
res=prod(res,res) #得到上述的(m^k)^2
if n%2==1: # n%2表示n被2除的余數(shù)
res=prod(res,m) #如果n是奇數(shù)，那么結(jié)果還要再乘以m
return res
m=(1,1,1,0) #初始化矩陣
(a,b,c,d)=pui(m,n-1) # n次冪的第一項是F(n+1)
return a
這里用到的乘方算法，對于奇數(shù)2k+1，只要先算k次冪，然后自乘，再乘以最初的矩陣；對于偶數(shù)2k，只需先算k次冪，然后自乘即可。而計算k次冪時仍然可以采用上面的算法。如果n在2進(jìn)制表達(dá)中一共有m位，并且其中有l(wèi)個1，那么一共需要進(jìn)行m+l次乘法，小于2*m=O(log n)。
多說無益，讓我們來看看三種算法處理相同規(guī)模的輸入各自要多少時間：
def timing(f,n):
'''計算f(n)需要多少時間'''
import time #載入時間模塊
t1=time.time() #讀取當(dāng)前時刻（計算開始時刻）
res=f(n) #計算f(n)
t2=time.time() #再次讀取當(dāng)前時刻（計算結(jié)束時刻）
return t2-t1 #兩次時刻差值既是計算f(n)所需要的時間，單位為秒
第一種天然呆的算法果然弱爆了，算F(30)就要0.6秒；第二種算法算十萬要3秒多；第三種算法算一百萬也不過3秒不到。上面的算法有一個問題，就是明明第二種算法是線性的，第三種算法是對數(shù)級的，但是當(dāng)我嘗試多加一個0時，所需要的時間完全不能忍受，不得不強(qiáng)制停止，大大超過按照前幾次測試推算的結(jié)果。為什么呢？答案就在于，斐波那契的兔子繁殖特別快，中間過程的數(shù)值很快超過了2^32，python不得不啟用了大數(shù)運算。而數(shù)字越大，進(jìn)行乘法、加法運算所需要的時間也越長，不能再當(dāng)做常數(shù)時間。那么讓我們來看看下面這個簡化，只求計算結(jié)果的末7位，也就是說利用求余數(shù)的方法把所有的數(shù)字都限制在10^8以內(nèi)：
def fibo_1_bis(n):
'''
簡單遞歸方法求斐波那契數(shù)列第n項。
輸入變量n應(yīng)當(dāng)為正整數(shù)。(對非法輸入沒有警告）
'''
if n < 3:
res=1 #設(shè)定初始狀態(tài)：F(1)=F(2)=1
else:
res=(fibo_1(n-1)+fibo_1(n-2))%100000000 #遞歸公式
return res
def fibo_2_bis(n):
'''
通過遞歸方法求斐波那契數(shù)列第n項
變量n應(yīng)當(dāng)為正整數(shù)。（對非法輸入沒有警告）
記錄最后兩項計算結(jié)果
'''
a=1
b=1 #設(shè)定初始狀態(tài)，a=F(1),b=F(2)
for i in range(2,n):
a,b=(a+b)%100000000,a # 由數(shù)學(xué)歸納法易得第i步中a=F(i),b=F(i-1)
return a #循環(huán)結(jié)束時i=n，a=F(n)
def fibo_3_bis(n):
'''
將求斐波那契數(shù)列轉(zhuǎn)化為求2階矩陣n次冪問題。
'''
def prod(m1,m2):
'''
兩個矩陣的乘積
'''
a1,b1,c1,d1=m1
a2,b2,c2,d2=m2
return ((a1*a2+b1*c2)%100000000,(a1*b2+c1*d2)%100000000,(a2*c1+c2*d1)%100000000,(b2*c1+d1*d2)%100000000)
def pui(m,n):
'''
求一個矩陣m的n次冪。
如n=2k+1，則m^n=(m^k)^2*m;
如n=2k，則m^n=(m^k)^2。
'''
if n == 1:
return m
else:
res=pui(m,n//2) #上述的k=n//2，//表示帶余除法的商，例如 5//2 = 2
res=prod(res,res) #得到上述的(m^k)^2
if n%2==1: # n%2表示n被2除的余數(shù)
res=prod(res,m) #如果n是奇數(shù)，那么結(jié)果還要再乘以m
return res
m=(1,1,1,0) #初始化矩陣
(a,b,c,d)=pui(m,n-1) # n次冪的第一項是F(n+1)
return a
再來看看需要多少時間：
可以看到第一種算法需要的時間基本滿足斐波那契的遞推公式，和前面的預(yù)測相符；第二種算法需要的時間也和預(yù)測的線性增長相符；第三種算法，不管我輸入多少個0，都是瞬間給出答案，O(log n)級的算法真心屌爆了有沒有?。?！
附python文件fibo.py下載地址：
http://115.com/file/aqyjof34java--19.用矩陣求Fibonacci數(shù)列的第N項參考了網(wǎng)上的思路，寫了個Java版的：
Java代碼
public class Fibonacci {
final static int[] A={1,1,1,0};
public static void main(String[] args) {
int n=7;
for(int i=0;i<=n;i++){
int f=fibonacci(i);
System.out.print(f+" ");
}
}
static int fibonacci(int n){
if(n==0)return 0;
if(n==1)return 1;
if(n>1){
int[] re=power(n-1);
return re[0];//矩陣乘積的第00項為所求
}
return -1;
}
//a^n=a^(n/2)*a^(n/2) or a^n=a^(n/2)*a^(n/2)*a
static int[] power(int n){
int[] a=new int[4];
if(n==1){
a=A;
}
else if(n%2==0){
a=matixMultiply(power(n/2),power(n/2));
}else if(n%2==1){
int[] temp=matixMultiply(power(n/2),power(n/2));
a=matixMultiply(A,temp);
}
return a;
}
//矩陣乘法
// return A*B
static int[] matixMultiply(int[] a,int [] b){
int[] re=new int[4];
re[0]=a[0]*b[0]+a[1]*b[2];
re[1]=a[0]*b[1]+a[1]*b[3];
re[2]=a[2]*b[0]+a[3]*b[2];
re[3]=a[2]*b[1]+a[3]*b[3];
return re;
}
}
