算法分析

研究算法的最終目的就是如何花更少的時(shí)間，如何占用更少的內(nèi)存去完成相同的需求，并且也通過案例演示了不同算法之間時(shí)間耗費(fèi)和空間耗費(fèi)上的差異，但我們并不能將時(shí)間占用和空間占用量化，因此，接下來我們要學(xué)習(xí)有關(guān)算法時(shí)間耗費(fèi)和算法空間耗費(fèi)的描述和分析。有關(guān)算法時(shí)間耗費(fèi)分析，我們稱之為算法的時(shí)間復(fù)雜度分析，有關(guān)算法的空間耗費(fèi)分析，我們稱之為算法的空間復(fù)雜度分析。

算法的時(shí)間復(fù)雜度分析

我們要計(jì)算算法時(shí)間耗費(fèi)情況，首先我們得度量算法的執(zhí)行時(shí)間，那么如何度量呢？
事后分析估算方法：
比較容易想到的方法就是我們把算法執(zhí)行若干次，然后拿個(gè)計(jì)時(shí)器在旁邊計(jì)時(shí)，這種事后統(tǒng)計(jì)的方法看上去的確不錯(cuò)，并且也并非要我們真的拿個(gè)計(jì)算器在旁邊計(jì)算，因?yàn)橛?jì)算機(jī)都提供了計(jì)時(shí)的功能。這種統(tǒng)計(jì)方法主要是通過設(shè)計(jì)好的測試程序和測試數(shù)據(jù)，利用計(jì)算機(jī)計(jì)時(shí)器對(duì)不同的算法編制的程序的運(yùn)行時(shí)間進(jìn)行比較，從而確定算法效率的高低，但是這種方法有很大的缺陷：必須依據(jù)算法實(shí)現(xiàn)編制好的測試程序，通常要花費(fèi)大量時(shí)間和精力，測試完了如果發(fā)現(xiàn)測試的是非常糟糕的算法，那么之前所做的事情就全部白費(fèi)了，并且不同的測試環(huán)境(硬件環(huán)境)的差別導(dǎo)致測試的結(jié)果差異也很大。

public static void main(String[] args) {
long start = System.currentTimeMillis();
int sum = 0;
int n=100;
for (int i = 1; i <= n; i++) {
sum += i;
}
System.out.println("sum=" + sum);
long end = System.currentTimeMillis();
System.out.println(end-start);
}

事前分析估算方法：
在計(jì)算機(jī)程序編寫前，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算，經(jīng)過總結(jié)，我們發(fā)現(xiàn)一個(gè)高級(jí)語言編寫的程序程序在計(jì)算機(jī)
上運(yùn)行所消耗的時(shí)間取決于下列因素：
1.算法采用的策略和方案；
2.編譯產(chǎn)生的代碼質(zhì)量；
3.問題的輸入規(guī)模(所謂的問題輸入規(guī)模就是輸入量的多少)；
4.機(jī)器執(zhí)行指令的速度；

由此可見，拋開這些與計(jì)算機(jī)硬件、軟件有關(guān)的因素，一個(gè)程序的運(yùn)行時(shí)間依賴于算法的好壞和問題的輸入規(guī)模。
如果算法固定，那么該算法的執(zhí)行時(shí)間就只和問題的輸入規(guī)模有關(guān)系了。
我么再次以之前的求和案例為例，進(jìn)行分析。
需求：
計(jì)算1到100的和。
第一種解法：

如果輸入量為n為1，則需要計(jì)算1次；
如果輸入量n為1億，則需要計(jì)算1億次；
public static void main(String[] args) {
int sum = 0;//執(zhí)行1次
int n=100;//執(zhí)行1次
for (int i = 1; i <= n; i++) {//執(zhí)行了n+1次
sum += i;//執(zhí)行了n次
}
System.out.println("sum=" + sum);
}

第二種解法：

如果輸入量為n為1，則需要計(jì)算1次；
如果輸入量n為1億，則需要計(jì)算1次；
public static void main(String[] args) {
int sum = 0;//執(zhí)行1次
int n=100;//執(zhí)行1次
sum = (n+1)*n/2;//執(zhí)行1次
System.out.println("sum="+sum);
}

因此，當(dāng)輸入規(guī)模為n時(shí)，第一種算法執(zhí)行了1+1+(n+1)+n=2n+3次；第二種算法執(zhí)行了1+1+1=3次。如果我們把
第一種算法的循環(huán)體看做是一個(gè)整體，忽略結(jié)束條件的判斷，那么其實(shí)這兩個(gè)算法運(yùn)行時(shí)間的差距就是n和1的差
距。
為什么循環(huán)判斷在算法1里執(zhí)行了n+1次，看起來是個(gè)不小的數(shù)量，但是卻可以忽略呢？我們來看下一個(gè)例子：
需求：
計(jì)算100個(gè)1+100個(gè)2+100個(gè)3+...100個(gè)100的結(jié)果
代碼：

public static void main(String[] args) {
int sum=0;
int n=100;
for (int i = 1; i <=n ; i++) {
for (int j = 1; j <=n ; j++) {
sum+=i;
}
}
System.out.println("sum="+sum);
}

上面這個(gè)例子中，如果我們要精確的研究循環(huán)的條件執(zhí)行了多少次，是一件很麻煩的事情，并且，由于真正計(jì)算和的代碼是內(nèi)循環(huán)的循環(huán)體，所以，在研究算法的效率時(shí)，我們只考慮核心代碼的執(zhí)行次數(shù)，這樣可以簡化分析。
我們研究算法復(fù)雜度，側(cè)重的是當(dāng)輸入規(guī)模不斷增大時(shí)，算法的增長量的一個(gè)抽象(規(guī)律)，而不是精確地定位需要執(zhí)行多少次，因?yàn)槿绻沁@樣的話，我們又得考慮回編譯期優(yōu)化等問題，容易主次跌倒。我們不關(guān)心編寫程序所用的語言是什么，也不關(guān)心這些程序?qū)⑴茉谑裁礃拥挠?jì)算機(jī)上，我們只關(guān)心它所實(shí)現(xiàn)的算法。這樣，不計(jì)那些循環(huán)索引的遞增和循環(huán)終止的條件、變量聲明、打印結(jié)果等操作，最終在分析程序的運(yùn)行時(shí)間時(shí)，最重要的是把程序看做是獨(dú)立于程序設(shè)計(jì)語言的算法或一系列步驟。我們分析一個(gè)算法的運(yùn)行時(shí)間，最重要的就是把核心操作的次數(shù)和輸入規(guī)模關(guān)聯(lián)起來。

函數(shù)漸近增長

給定兩個(gè)函數(shù)f(n)和g(n),如果存在一個(gè)整數(shù)N，使得對(duì)于所有的n>N,f(n)總是比g(n)大，那么我們說f(n)的增長漸近快于g(n)。
概念似乎有點(diǎn)艱澀難懂，那接下來我們做幾個(gè)測試。
測試一：
假設(shè)四個(gè)算法的輸入規(guī)模都是n：
1.算法A1要做2n+3次操作，可以這么理解：先執(zhí)行n次循環(huán)，執(zhí)行完畢后，再有一個(gè)n次循環(huán)，最后有3次運(yùn)算；
2.算法A2要做2n次操作；
3.算法B1要做3n+1次操作，可以這個(gè)理解：先執(zhí)行n次循環(huán)，再執(zhí)行一個(gè)n次循環(huán)，再執(zhí)行一個(gè)n次循環(huán)，最后有1
次運(yùn)算。
4.算法B2要做3n次操作；
那么，上述算法，哪一個(gè)更快一些呢？

通過數(shù)據(jù)表格，比較算法A1和算法B1：
當(dāng)輸入規(guī)模n=1時(shí)，A1需要執(zhí)行5次，B1需要執(zhí)行4次，所以A1的效率比B1的效率低；
當(dāng)輸入規(guī)模n=2時(shí)，A1需要執(zhí)行7次，B1需要執(zhí)行7次，所以A1的效率和B1的效率一樣；
當(dāng)輸入規(guī)模n>2時(shí)，A1需要的執(zhí)行次數(shù)一直比B1需要執(zhí)行的次數(shù)少，所以A1的效率比B1的效率高；
所以我們可以得出結(jié)論：

當(dāng)輸入規(guī)模n>2時(shí)，算法A1的漸近增長小于算法B1 的漸近增長
通過觀察折線圖，我們發(fā)現(xiàn)，隨著輸入規(guī)模的增大，算法A1和算法A2逐漸重疊到一塊，算法B1和算法B2逐漸重疊
到一塊，所以我們得出結(jié)論：
隨著輸入規(guī)模的增大，算法的常數(shù)操作可以忽略不計(jì)
測試二：
假設(shè)四個(gè)算法的輸入規(guī)模都是n：
1.算法C1需要做4n+8次操作
2.算法C2需要做n次操作
3.算法D1需要做2n^2次操作
4.算法D2需要做n^2次操作
那么上述算法，哪個(gè)更快一些？

?通過數(shù)據(jù)表格，對(duì)比算法C1和算法D1：
當(dāng)輸入規(guī)模n<=3時(shí)，算法C1執(zhí)行次數(shù)多于算法D1，因此算法C1效率低一些；
當(dāng)輸入規(guī)模n>3時(shí)，算法C1執(zhí)行次數(shù)少于算法D1，因此，算法D2效率低一些，
所以，總體上，算法C1要優(yōu)于算法D1.?

通過折線圖，對(duì)比對(duì)比算法C1和C2：
隨著輸入規(guī)模的增大，算法C1和算法C2幾乎重疊
通過折線圖，對(duì)比算法C系列和算法D系列：
隨著輸入規(guī)模的增大，即使去除n^2前面的常數(shù)因子，D系列的次數(shù)要遠(yuǎn)遠(yuǎn)高于C系列。
因此，可以得出結(jié)論：
隨著輸入規(guī)模的增大，與最高次項(xiàng)相乘的常數(shù)可以忽略
測試三：
假設(shè)四個(gè)算法的輸入規(guī)模都是n：
算法E1:
2n^2+3n+1;
算法E2：
n^2
算法F1：
2n^3+3n+1
算法F2：
n^3
那么上述算法，哪個(gè)更快一些？

?通過數(shù)據(jù)表格，對(duì)比算法E1和算法F1：
當(dāng)n=1時(shí)，算法E1和算法F1的執(zhí)行次數(shù)一樣；
當(dāng)n>1時(shí)，算法E1的執(zhí)行次數(shù)遠(yuǎn)遠(yuǎn)小于算法F1的執(zhí)行次數(shù)；
所以算法E1總體上是由于算法F1的。
通過折線圖我們會(huì)看到，算法F系列隨著n的增長會(huì)變得特塊，算法E系列隨著n的增長相比較算法F來說，變得比較慢，所以可以得出結(jié)論：
最高次項(xiàng)的指數(shù)大的，隨著n的增長，結(jié)果也會(huì)變得增長特別快?

算法時(shí)間復(fù)雜度

?大O記法
定義：
在進(jìn)行算法分析時(shí)，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)，進(jìn)而分析T(n)隨著n的變化情況并確定T(n)的量級(jí)。算法的時(shí)間復(fù)雜度，就是算法的時(shí)間量度，記作:T(n)=O(f(n))。它表示隨著問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度，其中f(n)是問題規(guī)模n的某個(gè)函數(shù)。
在這里，我們需要明確一個(gè)事情：執(zhí)行次數(shù)=執(zhí)行時(shí)間
用大寫O()來體現(xiàn)算法時(shí)間復(fù)雜度的記法，我們稱之為大O記法。一般情況下，隨著輸入規(guī)模n的增大，T(n)增長最
慢的算法為最優(yōu)算法。
下面我們使用大O表示法來表示一些求和算法的時(shí)間復(fù)雜度：
算法一：

public static void main(String[] args) {
int sum = 0;//執(zhí)行1次
int n=100;//執(zhí)行1次
sum = (n+1)*n/2;//執(zhí)行1次
System.out.println("sum="+sum);
}

算法二：

public static void main(String[] args) {
int sum = 0;//執(zhí)行1次
int n=100;//執(zhí)行1次
for (int i = 1; i <= n; i++) {
sum += i;//執(zhí)行了n次
}
System.out.println("sum=" + sum);
}

public static void main(String[] args) {
int sum=0;//執(zhí)行1次
int n=100;//執(zhí)行1次
for (int i = 1; i <=n ; i++) {
for (int j = 1; j <=n ; j++) {
sum+=i;//執(zhí)行n^2次
}
}
System.out.println("sum="+sum);
}

如果忽略判斷條件的執(zhí)行次數(shù)和輸出語句的執(zhí)行次數(shù)，那么當(dāng)輸入規(guī)模為n時(shí)，以上算法執(zhí)行的次數(shù)分別為：
算法一：3次
算法二：n+3次
算法三：n^2+2次
如果用大O記法表示上述每個(gè)算法的時(shí)間復(fù)雜度，應(yīng)該如何表示呢？基于我們對(duì)函數(shù)漸近增長的分析，推導(dǎo)大O階
的表示法有以下幾個(gè)規(guī)則可以使用：
1.用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)；
2.在修改后的運(yùn)行次數(shù)中，只保留高階項(xiàng)；
3.如果最高階項(xiàng)存在，且常數(shù)因子不為1，則去除與這個(gè)項(xiàng)相乘的常數(shù)；
所以，上述算法的大O記法分別為：
算法一：O(1)
算法二：O(n)

算法的空間復(fù)雜度分析

計(jì)算機(jī)的軟硬件都經(jīng)歷了一個(gè)比較漫長的演變史，作為為運(yùn)算提供環(huán)境的內(nèi)存，更是如此，從早些時(shí)候的512k,經(jīng)
歷了1M，2M，4M...等，發(fā)展到現(xiàn)在的8G，甚至16G和32G，所以早期，算法在運(yùn)行過程中對(duì)內(nèi)存的占用情況也是
一個(gè)經(jīng)常需要考慮的問題。我么可以用算法的空間復(fù)雜度來描述算法對(duì)內(nèi)存的占用。
java中常見內(nèi)存占用
1.基本數(shù)據(jù)類型內(nèi)存占用情況：

?計(jì)算機(jī)訪問內(nèi)存的方式都是一次一個(gè)字節(jié)

一個(gè)引用（機(jī)器地址）需要8個(gè)字節(jié)表示：
例如： Date date = new Date(),則date這個(gè)變量需要占用8個(gè)字節(jié)來表示
4.創(chuàng)建一個(gè)對(duì)象，比如new Date()，除了Date對(duì)象內(nèi)部存儲(chǔ)的數(shù)據(jù)(例如年月日等信息)占用的內(nèi)存，該對(duì)象本身也有內(nèi)存開銷，每個(gè)對(duì)象的自身開銷是16個(gè)字節(jié)，用來保存對(duì)象的頭信息。
5.一般內(nèi)存的使用，如果不夠8個(gè)字節(jié)，都會(huì)被自動(dòng)填充為8字節(jié)：

?

6.java中數(shù)組被被限定為對(duì)象，他們一般都會(huì)因?yàn)橛涗涢L度而需要額外的內(nèi)存，一個(gè)原始數(shù)據(jù)類型的數(shù)組一般需要24字節(jié)的頭信息(16個(gè)自己的對(duì)象開銷，4字節(jié)用于保存長度以及4個(gè)填充字節(jié))再加上保存值所需的內(nèi)存。?

算法的空間復(fù)雜度
了解了java的內(nèi)存最基本的機(jī)制，就能夠有效幫助我們估計(jì)大量程序的內(nèi)存使用情況。
算法的空間復(fù)雜度計(jì)算公式記作：S(n)=O(f(n)),其中n為輸入規(guī)模，f(n)為語句關(guān)于n所占存儲(chǔ)空間的函數(shù)。
案例：
對(duì)指定的數(shù)組元素進(jìn)行反轉(zhuǎn)，并返回反轉(zhuǎn)的內(nèi)容。
解法一：

public static int[] reverse1(int[] arr){
int n=arr.length;//申請(qǐng)4個(gè)字節(jié)
int temp;//申請(qǐng)4個(gè)字節(jié)
for(int start=0,end=n-1;start<=end;start++,end--){
temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
}
return arr;
}

解法二：

public static int[] reverse2(int[] arr){
int n=arr.length;//申請(qǐng)4個(gè)字節(jié)
int[] temp=new int[n];//申請(qǐng)n*4個(gè)字節(jié)+數(shù)組自身頭信息開銷24個(gè)字節(jié)
for (int i = n-1; i >=0; i--) {
temp[n-1-i]=arr[i];
}
return temp;
}

忽略判斷條件占用的內(nèi)存，我們得出的內(nèi)存占用情況如下：
算法一：
不管傳入的數(shù)組大小為多少，始終額外申請(qǐng)4+4=8個(gè)字節(jié)；
算法二：
4+4n+24=4n+28;
根據(jù)大O推導(dǎo)法則，算法一的空間復(fù)雜度為O(1),算法二的空間復(fù)雜度為O(n),所以從空間占用的角度講，算法一要
優(yōu)于算法二。
由于java中有內(nèi)存垃圾回收機(jī)制，并且jvm對(duì)程序的內(nèi)存占用也有優(yōu)化（例如即時(shí)編譯），我們無法精確的評(píng)估一個(gè)java程序的內(nèi)存占用情況，但是了解了java的基本內(nèi)存占用，使我們可以對(duì)java程序的內(nèi)存占用情況進(jìn)行估算。
由于現(xiàn)在的計(jì)算機(jī)設(shè)備內(nèi)存一般都比較大，基本上個(gè)人計(jì)算機(jī)都是4G起步，大的可以達(dá)到32G，所以內(nèi)存占用一般情況下并不是我們算法的瓶頸，普通情況下直接說復(fù)雜度，默認(rèn)為算法的時(shí)間復(fù)雜度。但是，如果你做的程序是嵌入式開發(fā)，尤其是一些傳感器設(shè)備上的內(nèi)置程序，由于這些設(shè)備的內(nèi)存很小，一般為幾kb，這個(gè)時(shí)候?qū)λ惴ǖ目臻g復(fù)雜度就有要求了，但是一般做java開發(fā)的，基本上都是服務(wù)器開發(fā)，一般不存在這樣的問題。