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