一、算法分析

前面我們已經介紹了，研究算法的最終目的就是如何花更少的時間，如何占用更少的內存去完成相同的需求，并且 也通過案例演示了不同算法之間時間耗費和空間耗費上的差異，但我們并不能將時間占用和空間占用量化，因此， 接下來我們要學習有關算法時間耗費和算法空間耗費的描述和分析。有關算法時間耗費分析，我們稱之為算法的時 間復雜度分析，有關算法的空間耗費分析，我們稱之為算法的空間復雜度分析。

0.1 算法的時間復雜度分析

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

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);
}

事前分析估算方法：
在計算機程序編寫前，依據統計方法對算法進行估算，經過總結，我們發現一個高級語言編寫的程序程序在計算機 上運行所消耗的時間取決于下列因素：

1. 算法采用的策略和方案；
2. 編譯產生的代碼質量；
3. 問題的輸入規模(所謂的問題輸入規模就是輸入量的多少)；
4. 機器執行指令的速度；

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

1. 如果輸入量為n為1，則需要計算1次；
2. 如果輸入量n為1億，則需要計算1億次；

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

第二種解法：

1. 如果輸入量為n為1，則需要計算1次；
2. 如果輸入量n為1億，則需要計算1次；

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

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

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); }

上面這個例子中，如果我們要精確的研究循環的條件執行了多少次，是一件很麻煩的事情，并且，由于真正計算和 的代碼是內循環的循環體，所以，在研究算法的效率時，我們只考慮核心代碼的執行次數，這樣可以簡化分析。
我們研究算法復雜度，側重的是當輸入規模不斷增大時，算法的增長量的一個抽象(規律)，而不是精確地定位需要 執行多少次，因為如果是這樣的話，我們又得考慮回編譯期優化等問題，容易主次跌倒。
我們不關心編寫程序所用的語言是什么，也不關心這些程序將跑在什么樣的計算機上，我們只關心它所實現的算 法。這樣，不計那些循環索引的遞增和循環終止的條件、變量聲明、打印結果等操作，最終在分析程序的運行時間 時，最重要的是把程序看做是獨立于程序設計語言的算法或一系列步驟。我們分析一個算法的運行時間，最重要的 就是把核心操作的次數和輸入規模關聯起來。

0.1.1 函數漸近增長

概念：

定兩個函數f(n)和g(n),如果存在一個整數N，使得對于所有的n>N,f(n)總是比g(n)大，那么我們說f(n)的增長漸近 快于g(n)。
概念似乎有點艱澀難懂，那接下來我們做幾個測試。測試一：
假設四個算法的輸入規模都是n：

1. 算法A1要做2n+3次操作，可以這么理解：先執行n次循環，執行完畢后，再有一個n次循環，最后有3次運算；
2. 算法A2要做2n次操作；
3. 算法B1要做3n+1次操作，可以這個理解：先執行n次循環，再執行一個n次循環，再執行一個n次循環，最后有1

次運算。

1. 算法B2要做3n次操作；

那么，上述算法，哪一個更快一些呢？

通過數據表格，比較算法A1和算法B1：
當輸入規模n=1時，A1需要執行5次，B1需要執行4次，所以A1的效率比B1的效率低； 當輸入規模n=2時，A1需要執行7次，B1需要執行7次，所以A1的效率和B1的效率一樣；
當輸入規模n>2時，A1需要的執行次數一直比B1需要執行的次數少，所以A1的效率比B1的效率高；
所以我們可以得出結論：

輸入規模n>2時，算法A1的漸近增長小于算法B1 的漸近增長

通過觀察折線圖，我們發現，隨著輸入規模的增大，算法A1和算法A2逐漸重疊到一塊，算法B1和算法B2逐漸重疊 到一塊，所以我們得出結論：

隨著輸入規模的增大，算法的常數操作可以忽略不計測試二：

假設四個算法的輸入規模都是n：

1. 算法C1需要做4n+8次操作
2. 算法C2需要做n次操作
3. 算法D1需要做2n^2次操作
4. 算法D2需要做n^2次操作

那么上述算法，哪個更快一些？

通過數據表格，對比算法C1和算法D1：
當輸入規模n<=3時，算法C1執行次數多于算法D1，因此算法C1效率低一些； 當輸入規模n>3時，算法C1執行次數少于算法D1，因此，算法D2效率低一些， 所以，總體上，算法C1要優于算法D1.

過折線圖，對比對比算法C1和C2：
隨著輸入規模的增大，算法C1和算法C2幾乎重疊通過折線圖，對比算法C系列和算法D系列：
隨著輸入規模的增大，即使去除n^2前面的常數因子，D系列的次數要遠遠高于C系列。

因此，可以得出結論：

隨著輸入規模的增大，與最高次項相乘的常數可以忽略

測試三：
假設四個算法的輸入規模都是n： 算法E1:
2n^2+3n+1;
算法E2：
n^2
算法F1：
2n^3+3n+1 算法F2： n^3
那么上述算法，哪個更快一些？

通過數據表格，對比算法E1和算法F1：
當n=1時，算法E1和算法F1的執行次數一樣；
當n>1時，算法E1的執行次數遠遠小于算法F1的執行次數； 所以算法E1總體上是由于算法F1的。
通過折線圖我們會看到，算法F系列隨著n的增長會變得特塊，算法E系列隨著n的增長相比較算法F來說，變得比較 慢，所以可以得出結論：

最高次項的指數大的，隨著n的增長，結果也會變得增長特別快

測試四：
假設五個算法的輸入規模都是n： 算法G：
n^3;
算法H:
n^2;
算法I：
n:
算法J：
logn
算法K:
1
那么上述算法，哪個效率更高呢？

通過觀察數據表格和折線圖，很容易可以得出結論： 算法函數中n最高次冪越小，算法效率越高
總上所述，在我們比較算法隨著輸入規模的增長量時，可以有以下規則：

1 算法函數中的常數可以忽略；

1. 算法函數中最高次冪的常數因子可以忽略；
2. 算法函數中最高次冪越小，算法效率越高。

1.1 算法時間復雜度

1.1.1 大O記法

定義：

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

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

算法二：

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

算法三：

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

如果忽略判斷條件的執行次數和輸出語句的執行次數，那么當輸入規模為n時，以上算法執行的次數分別為： 算法一：3次
算法二：n+3次 算法三：n^2+2次
如果用大O記法表示上述每個算法的時間復雜度，應該如何表示呢？基于我們對函數漸近增長的分析，推導大O階 的表示法有以下幾個規則可以使用：

2 用常數1取代運行時間中的所有加法常數；

1. 在修改后的運行次數中，只保留高階項；
2. **如果最高階項存在，且常數因子不為1，則去除與這個項相乘的常數； **所以，上述算法的大O記法分別為：

算法一：O(1) 算法二：O(n)

算法三：O(n^2)

2.1 常見的大O階

3 線性階

一般含有非嵌套循環涉及線性階，線性階就是隨著輸入規模的擴大，對應計算次數呈直線增長，例如：

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

上面這段代碼，它的循環的時間復雜度為O(n),因為循環體中的代碼需要執行n次

4 平方階

一般嵌套循環屬于這種時間復雜度

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

上面這段代碼，n=100，也就是說，外層循環每執行一次，內層循環就執行100次，那總共程序想要從這兩個循環 中出來，就需要執行100*100次，也就是n的平方次，所以這段代碼的時間復雜度是O(n^2).

5 立方階

一般三層嵌套循環屬于這種時間復雜度

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

上面這段代碼，n=100，也就是說，外層循環每執行一次，中間循環循環就執行100次，中間循環每執行一次，最 內層循環需要執行100次，那總共程序想要從這三個循環中出來，就需要執行100_100_100次，也就是n的立方，所 以這段代碼的時間復雜度是O(n^3).

6 對數階

對數，屬于高中數學的內容，我們分析程序以程序為主，數學為輔，所以不用過分擔心。

1 int i=1,n=100;
2 while(i<n){ 3 i = i*2; 4 }

由于每次i*2之后，就距離n更近一步，假設有x個2相乘后大于n，則會退出循環。由于是2^x=n,得到x=log(2)n,所 以這個循環的時間復雜度為O(logn);
對于對數階，由于隨著輸入規模n的增大，不管底數為多少，他們的增長趨勢是一樣的，所以我們會忽略底數。

7 常數階

一般不涉及循環操作的都是常數階，因為它不會隨著n的增長而增加操作次數。例如：

public static void main(String[] args) { int n=100;int i=n+2;System.out.println(i); 
}

上述代碼，不管輸入規模n是多少，都執行2次，根據大O推導法則，常數用1來替換，所以上述代碼的時間復雜度 為O(1)
下面是對常見時間復雜度的一個總結：

描述	增長的數量級	說明	舉例
常數級別	1	普通語句	將兩個數相加
對數級別	logN	二分策略	二分查找
線性級別	N	循環	找出最大元素
線型對數級別	NlogN	分治思想	歸并排序
平方級別	N^2	雙層循環	檢查所有元素對
立方級別	N^3	三層循環	檢查所有三元組
指數級別	2^N	窮舉查找	檢查所有子集

他們的復雜程度從低到高依次為：
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n3)
根據前面的折線圖分析，我們會發現，從平方階開始，隨著輸入規模的增大，時間成本會急劇增大，所以，我們的 算法，盡可能的追求的是O(1),O(logn),O(n),O(nlogn)這幾種時間復雜度，而如果發現算法的時間復雜度為平方階、 立方階或者更復雜的，那我們可以分為這種算法是不可取的，需要優化。

7.1 函數調用的時間復雜度分析

之前，我們分析的都是單個函數內，算法代碼的時間復雜度，接下來我們分析函數調用過程中時間復雜度。 案例一：

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

在main方法中，有一個for循環，循環體調用了show方法，由于show方法內部只執行了一行代碼，所以show方法 的時間復雜度為O(1),那main方法的時間復雜度就是O(n)

案例二：

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

在main方法中，有一個for循環，循環體調用了show方法，由于show方法內部也有一個for循環，所以show方法 的時間復雜度為O(n),那main方法的時間復雜度為O(n^2)

案例三：

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

在show方法中，有一個for循環，所以show方法的時間復雜度為O(n),在main方法中，show(n)這行代碼內部執行 的次數為n，第一個for循環內調用了show方法，所以其執行次數為n^2,第二個嵌套for循環內只執行了一行代碼， 所以其執行次數為n^{2,那么main方法總執行次數為n+n}2+n²⁼²ⁿ2+n。根據大O推導規則，去掉n保留最高階項，并去掉最高階項的常數因子2，所以最終main方法的時間復雜度為O(n^2)

7.1.1 最壞情況

從心理學角度講，每個人對發生的事情都會有一個預期，比如看到半杯水，有人會說：哇哦，還有半杯水哦！但也 有人會說：天哪，只有半杯水了。一般人處于一種對未來失敗的擔憂，而在預期的時候趨向做最壞的打算，這樣即 使最糟糕的結果出現，當事人也有了心理準備，比較容易接受結果。假如最糟糕的結果并沒有出現，當事人會很快 樂。
算法分析也是類似，假如有一個需求：
有一個存儲了n個隨機數字的數組，請從中查找出指定的數字。

public int search(int num){int[] arr={11,10,8,9,7,22,23,0};for (int i = 0; i < arr.length; i++) {if (num==arr[i]){return i;}}return -1; 
}

最好情況：

查找的第一個數字就是期望的數字，那么算法的時間復雜度為O(1) 最壞情況：
查找的最后一個數字，才是期望的數字，那么算法的時間復雜度為O(n) 平均情況：
任何數字查找的平均成本是O(n/2)
最壞情況是一種保證，在應用中，這是一種最基本的保障，即使在最壞情況下，也能夠正常提供服務，所以，除非 特別指定，我們提到的運行時間都指的是最壞情況下的運行時間。

7.2 算法的空間復雜度分析

計算機的軟硬件都經歷了一個比較漫長的演變史，作為為運算提供環境的內存，更是如此，從早些時候的512k,經 歷了1M，2M，4M…等，發展到現在的8G，甚至16G和32G，所以早期，算法在運行過程中對內存的占用情況也是 一個經常需要考慮的問題。我么可以用算法的空間復雜度來描述算法對內存的占用。

7.2.1 java中常見內存占用

1. 基本數據類型內存占用情況：

數據類型	內存占用字節數
byte	1
short	2
int	4
long	8
?oat	4
double	8
boolean	1
char	2

1. 計算機訪問內存的方式都是一次一個字節

1. 一個引用（機器地址）需要8個字節表示：

例如： Date date = new Date(),則date這個變量需要占用8個字節來表示

1. 創建一個對象，比如new Date()，除了Date對象內部存儲的數據(例如年月日等信息)占用的內存，該對象本身也有內存開銷，每個對象的自身開銷是16個字節，用來保存對象的頭信息。
2. 一般內存的使用，如果不夠8個字節，都會被自動填充為8字節：

1. java中數組被被限定為對象，他們一般都會因為記錄長度而需要額外的內存，一個原始數據類型的數組一般需要

24字節的頭信息(16個自己的對象開銷，4字節用于保存長度以及4個填充字節)再加上保存值所需的內存。

7.2.2 算法的空間復雜度

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

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

解法二：

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

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