1.算法效率
- 算法效率分析分為兩種：第一種是時間效率，第二種是空間效率。 時間效率被稱為時間複雜度，而空間效率被稱作空間複雜度。
- 時間複雜度主要衡量的是一個算法的運作速度，而空間複雜度主要衡量一個算法所需要的額外空間。
2.時間複雜度
2.1 時間複雜度的概念
- 時間複雜度的定義：
在計算機科學中，算法的時間複雜度是一個函數，它定量描述了該算法的運作時間。
- 但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，是以才有了時間複雜度這個分析方式。
一個算法所花費的時間與其中語句的執行次數成正比例，算法中的基本操作的執行次數為算法的時間複雜度。
2.2 大O的漸進表示法
// 請計算一下func1基本操作執行了多少次？
void func1(int N){
int count = 0;
for (int i = 0; i < N ; i++) {
for (int j = 0; j < N ; j++) {
count++; }
}
for (int k = 0; k < 2 * N ; k++) {
count++;
}
int M = 10;
while ((M--) > 0) {
count++;
}
System.out.println(count);
}
Func1 執行的基本操作次數 ：
F(N) = N ^ 2 + 2 * N +10
N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010
實際中我們計算時間複雜度時，我們其實并不一定要計算精确的執行次數，而隻需要大概執行次數，那麼這裡可以我們使用大O的漸進表示法。
大O符号（Big O notation）：是用于描述函數漸進行為的數學符号。
推導大O階方法：
1、用常數1取代運作時間中的所有加法常數。
2、在修改後的運作次數函數中，隻保留最高階項。
3、如果最高階項存在且不是1，則去除與這個項目相乘的常數。
使用大O的漸進表示法以後，Func1的時間複雜度為：
N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000
大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數。
另外有些算法的時間複雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規模的最大運作次數(上界)
平均情況：任意輸入規模的期望運作次數
最好情況：任意輸入規模的最小運作次數(下界)
例如
：
在一個長度為N數組中搜尋一個資料x
最好情況：1次找到
最壞情況：N次找到
平均情況：N/2次找到
在實際中一般情況關注的是算法的最壞運作情況，是以數組中搜尋資料時間複雜度為O(N)
Tips:不可以通過程式的執行時間來衡量算法的時間複雜度（）不同的電腦可能有不同的配置）
2.3常見時間複雜度計算舉例
執行個體1：
// 計算func2的時間複雜度？
void func2(int N) {
int count = 0;
for (int k = 0; k < 2 * N ; k++) {
count++; }
int M = 10;
while ((M--) > 0) {
count++; }
System.out.println(count);
}
執行個體2：
// 計算func3的時間複雜度？
void func3(int N, int M) {
int count = 0;
for (int k = 0; k < M; k++) {
count++; }
for (int k = 0; k < N ; k++) {
count++; }
System.out.println(count);
}
執行個體3：
// 計算func4的時間複雜度？
void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
count++; }
System.out.println(count);
}
執行個體4：
// 計算bubbleSort的時間複雜度？
void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
boolean sorted = true;
for (int i = 1; i < end; i++) {
if (array[i - 1] > array[i]) {
Swap(array, i - 1, i);
sorted = false; } }
if (sorted == true) {
break; }
}
}
執行個體5：
// 計算binarySearch的時間複雜度？
int binarySearch(int[] array, int value) {
int begin = 0;
int end = array.length - 1;
while (begin <= end) {
int mid = begin + ((end-begin) / 2);
if (array[mid] < value)
begin = mid + 1;
else if (array[mid] > value)
end = mid - 1;
else
return mid;
}
return -1;
}
執行個體6：
// 計算階乘遞歸factorial的時間複雜度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N; }
執行個體8：
// 計算斐波那契遞歸fibonacci的時間複雜度？
int fibonacci(int N) {
return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}
執行個體答案及分析：
1. 執行個體1基本操作執行了2N+10次，通過推導大O階方法知道，時間複雜度為 O(N)
2. 執行個體2基本操作執行了M+N次，有兩個未知數M和N，時間複雜度為 O(N+M)
3. 執行個體3基本操作執行了100次，通過推導大O階方法，時間複雜度為 O(1)
4. 執行個體4基本操作執行最好N次，最壞執行了
(N*(N-1))/2次，
通過推導大O階方法+時間複雜度一般看最壞，時間複雜度為 O(N^2)
5. 執行個體5基本操作執行最好1次，最壞O(logN)次，時間複雜度為 O(logN)
ps：logN在算法分析中表示是底數為2，對數為N
。有些地方會寫成lgN。（建議通過折紙查找的方式講解logN是怎麼計算出來的）(因為二分查找每次排除掉一半的不适合值,一次二分剩下：n/2 兩次二分剩下：n/2/2 = n/4)
6. 執行個體6通過計算分析發現基本操作遞歸了N次，時間複雜度為O(N)。
7. 執行個體7通過計算分析發現基本操作遞歸了2^N 次，時間複雜度為O(2^N)。
3.空間複雜度
- 空間複雜度是對一個算法在運作過程中臨時占用存儲空間大小的量度 。
- 空間複雜度不是程式占用了多少bytes的空間，因為這個也沒太大意義，是以空間複雜度算的是變量的個數。
-
空間複雜度計算規則基本跟時間複雜度類似，也使用大O漸進表示法。
執行個體1：
// 計算bubbleSort的空間複雜度？
void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
boolean sorted = true;
for (int i = 1; i < end; i++) {
if (array[i - 1] > array[i]) {
Swap(array, i - 1, i);
sorted = false; } }
if (sorted == true) {
break; }
}
}
執行個體2：
// 計算fibonacci的空間複雜度？
int[] fibonacci(int n) {
long[] fibArray = new long[n + 1];
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n ; i++) {
fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
}
return fibArray;
}
執行個體3：
// 計算階乘遞歸Factorial的時間複雜度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N; }
執行個體答案及分析：
1. 執行個體1使用了常數個額外空間，是以空間複雜度為 O(1)
2. 執行個體2動态開辟了N個空間，空間複雜度為 O(N)
3. 執行個體3遞歸調用了N次，開辟了N個棧幀，每個棧幀使用了常數個空間。空間複雜度為O(N)
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)