1.算法好壞的度量方法
- 事后統(tǒng)計方法：用設計好的測試程序和數據，對完成的算法進行測試，從而確定算法效率的高低
- 事先分析估算方法：在實現算法之前，使用事先統(tǒng)計方法對算法進行估算
考慮到成本和不同機器的差異，我們在解決問題選取一個算法時，一般采用事先分析估算方法
2. 事先分析估算的衡量標準
我們如何事先來衡量一個算法的好壞呢？當然是既要馬兒跑得快，又要馬兒吃得少
可以從下面兩個方面來衡量：
- 時間復雜度：跑得快，就是算法效率的體現，對于同一規(guī)模的輸入，處理的時間越快，算法越好
- 空間復雜度：吃得少，就是算法開銷的體現，對于同一規(guī)模的輸入，算法所需存儲空間的開銷越低，算法越好
總結：使用時間復雜度和空間復雜度來事先評判一個算法的好壞
3. 時間復雜度
3.1 定義
時間復雜度就是用來衡量程序隨著輸入規(guī)模的增大，程序需要執(zhí)行時間的增長規(guī)模。我們關注的是增長的量級，而不是具體的運行時間。
我們用下面的表達式來表示程序運行時間T(n)關于程序輸入規(guī)模n的關系
T(n) = O(f(n))
關于上面的表達式，做如下介紹：
T(n): 程序執(zhí)行時間關于數據輸入規(guī)模n的函數
O(f(n)): 大O時間復雜度表示法
f(n)：程序執(zhí)行代碼行數總和關于輸入規(guī)模n的函數
n: 數據輸入規(guī)模
我們可以這么理解上面的表達式：
程序的執(zhí)行時間T(n)和程序執(zhí)行代碼行數總和f(n)并不完全對等，因為我們的高級語言需要被解釋編譯才能被計算機執(zhí)行，但是它們有一定的關系，理論上說，程序需要執(zhí)行代碼行數的總和f(n)越多，需要執(zhí)行的時間T(n)就越長。所以，我們只需要關心執(zhí)行代碼行數的總和f(n)關于輸入規(guī)模n的增長規(guī)模，為了更好地表達增長量級，我們使用大O來表示。
3.2 計算方法
我們來計算1 + 2 + 3 + .... n 的和
有如下兩種算法
算法1:
private int method1(int n) {
int sum = 0; // 1次
for (int i = 1; i <= n; i++) { // n次
sum += i; // n次
}
return sum;
}
算法2:
private int method2(int n) {
return (n + 1) * n / 2; // 1次
}`
易知，兩個算法代碼執(zhí)行行數總和f(n)如下：
算法1： f(n) = 2n + 1
算法2： f(n) = 1
圖形表示如下所示：
可以看出，算法1中隨著輸入規(guī)模n的增長，f(n)呈線性增長; 而算法2，不管輸入規(guī)模n為多少，f(n)恒為1。
那我們如何用大O來表示時間復雜度呢？
既然是表示增長規(guī)模，我們就要重點關注主要影響因素，忽略次要影響因素，總結如下：
- 找出程序執(zhí)行代碼行數總和f(n)關于輸入規(guī)模n的函數，即f(n)
- 保留n的最高次項，去除其他次項，并把與最高次項相乘的常數設置為1
我們拿上面的兩個算法來舉例
首先，找到程序執(zhí)行代碼行數總和f(n)關于輸入規(guī)模n的函數f(n)，即：
f(n) = 2n + 1 和 f(n) = 1
保留n的最高次項，去除其他次項，并把與最高次項相乘的常數設置為1：
n 和 1
所以兩個算法的時間復雜度用大O表示為：
O(n) 和 O(1)
3.3 關于時間復雜度計算的探索
上面我們說到，計算時間復雜度的計算規(guī)則如下：
保留最高次項，并把與最高次項相乘的常數設置為1
根據這個規(guī)則，我們可以很輕易地算出下列算法的時間復雜度
| 序號 | 程序執(zhí)行代碼行數總和 | 時間復雜度 |
|---|---|---|
| 1 | f(n) = 1 | O(1) |
| 2 | f(n) = 3 | O(1) |
| 3 | f(n) = n + 1 | O(n) |
| 4 | f(n) = 2n + 1 | O(n) |
| 5 | f(n) = n^2 + 1 | O(n^2) |
| 6 | f(n) = n^2 + 2n + 1 | O(n^2) |
可以看到，雖然有6個算法，但是它們實際上只要3個時間復雜度來表示，分別為O(1)、O(n)、O(n^2)
我們把f(n)在圖形上呈現出來：
從圖形上可以看出
f(n) = n^2 + 2n + 1 和 f(n) = n^2 + 1 的增長規(guī)模是同一量級的，增長較快
f(n) = 2n + 1 和 f(n) = n + 1的增長規(guī)模是同一量級的，增長緩慢
f(n) = 3 和 f(n) = 1的增長規(guī)模是同一量級的，恒為常數，不增長
我們可以很容易地把6個算法分成3組，即它們對應的時間復雜度分別為：O(n^2)、O(n)、O(1)
3.4 如何在代碼層面快速看出時間復雜度
1. 抓大放小
根據上面的規(guī)則，我們只要關注最高次項，在代碼層面，只要關注最復雜的循環(huán)就可以了，比如下面的代碼
private void test(int n) {
int sum = 0; // 1 次
for (int i = 0; i < n; i++) {
sum = sum + i; // n 次
}
// 這里是最復雜的循環(huán)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; i++) {
sum = sum + i * j; // n^2 次
}
}
}
可以看出，f(n) = n^2 + n + 1，時間復雜度為O(n^2)。
在上面的代碼里，我們只要找最復雜的循環(huán)，即雙層循環(huán)，所以時間復雜度就是O(n^2)
2. O(n+m)
我們之前提到的數據輸入規(guī)模，一般都是單個輸入n，但程序可以存在多個輸入，比如下面的算法，程序執(zhí)行代碼的行數，受到n和m兩個參數的影響
private void oNAndM(int n, int m) {
int sum = 0; // 1 次
for (int i = 0; i < n; i++) {
sum = sum + i; // n 次
}
for (int i = 0; i < m; i++) {
sum = sum + i; // m 次
}
}
上面的f(n,m) = n + m + 1，因為不知道m(xù)和n的具體關系，所以m不能被忽略，這時候時間復雜度就是：O(n+m)
3. O(n * m)
上面提到的是n和m是平行的，沒有相互影響，所以是相加，而如果n、m是嵌套的，則需要相乘，如下：
private void oNMultM(int n, int m) {
int sum = 0; // 1 次
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; i++) {
sum = sum + i * j; // n * m 次
}
}
}
可以知道f(n,m) = n * m + 1，則時間復雜度為：O(n * m)
其實2次方階O(n^2)可以看成n和m相等的特殊情況
3.5 常見的時間復雜度
我們平?？吹降乃惴〞r間復雜度一般都是以下這幾種或這幾種的組合
| 序號 | 時間復雜度 | 名稱 |
|---|---|---|
| 1 | O(1) | 常數階 |
| 2 | O(logn) | 對數階 |
| 3 | O(n) | 線性階 |
| 4 | O(n^k) | k次方階 （比如k=2，即O(n^2)，則是平方階） |
我們來看看這幾種時間復雜度的算法體現
1. O(1)
f(n)不會隨輸入規(guī)模的n增大而變化
private void o1(int n) {
int i = n;
int sum = i * 2;
System.out.print("sum 為：" + sum);
}
可以看到，不管n為多少，f(n) 恒為3，就算f(n)恒為1000還是10000，時間復雜度都是O(1)
2. O(logn)
1. private int oLogn(int n) {
2. int i = 1;
3. while (i < n) {
4. i = i * 2;
5. }
6. return i;
7. }
可以看到，上述代碼，主要的執(zhí)行代碼是循環(huán)體中的第4行代碼，而上述的算法就是：i 初始化為1，每次循環(huán)乘以2，當 i > n時，結束循環(huán)，我們假設x次循環(huán)后，跳出循環(huán)，則i的值如下：
2^0、 2^1、 2^2.... 2^x ，所以滿足2^x >= n，則x >= log2n（這里的2是底數）
所以x就是第一個大于等于log2n的整數，對數可以相互轉換底數，且我們求的是數量級，所以我們可以不關心底數，直接用O(logn)來表示所有的對數階
3. O(n)
private int oN(int n) {
int sum = 1;
for (int i = 0; i < n; i ++) {
sum = sum + i;
}
return sum;
}
這種線性階，其實就是單個的for循環(huán)
4. O(n^2)
private void oN2(int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; i++) {
sum = sum + i * j; // n^2 次
}
}
}
這就是平方階，其實就是2個循環(huán)。如果3個循環(huán)，就是立方階，k個循環(huán)，就是k次方階
4. 空間復雜度
空間復雜度表示的是存儲空間跟數據輸入規(guī)模的增長關系。
算法所需的存儲空間可以使用如下表達式來表示：
S(n) = O(f(n))
跟時間復雜度類似，空間復雜度也是用大O來表示。
我們來分析如下兩個算法的空間復雜度
算法1
public void o1() {
int i =1; // 1個
}
可以看到，我們只需要申請一個存儲空間給i，所以空間復雜度為O(1)
算法2
public void oN(int n) {
int[] arr = new int[n]; // n個
}
易知，我們需要申請n個存儲空間給數組arr，所以空間復雜度為O(n)
關于空間復雜度的計算跟時間復雜度一樣，都是保留最高次項，并把與最高次項相乘的常數設置為1，這里就不詳細描述了
5. 復雜度的排序
對于我們常見的復雜度，從低階到高階的排序如下：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2)
評估一個算法，時間復雜度和空間復雜度，都是越低越好
6. 應用
在后續(xù)的學習中，不管是各種數據結構的CURD操作還是評判各種算法好壞，我們都會從時間復雜度和空間復雜度兩個方面來分析。
比如遍歷HashMap的時間復雜度是多少？快速排序的平均時間復雜度和空間復雜度是多少？
我們沒必要去記住它們，而是要懂得分析的方法，然后應用在日常的編程中，利于我們更好地選取數據結構和算法，你鋼鐵了，自然就戰(zhàn)士了
7. 思考
關于《智行火車票》把加速包開到最大搶到票以后，智行上不付錢，然后登錄12306在未完成訂單中以原價購買
如果你是智行的員工
- 這種情況可以從技術層面避免嗎？為什么？
- 如果不能避免，怎么去優(yōu)化？
