觀察
運(yùn)行時(shí)間和輸入本身相對(duì)無(wú)關(guān)，主要取決于問(wèn)題規(guī)模
例：統(tǒng)計(jì)文件中三個(gè)數(shù)和為0的數(shù)量
public class ThreeSum{
public static int count(int a[]){
int N = a.length, cnt = 0;
for(int i = 0; i < N; i++){
for(int j = i + 1; j < N; j++){
for (int k = j + 1; k < N; k++){
if(a[i] + a[j] + a[k] == 0)
cnt += 1;
}
}
}
}
}
一種表示計(jì)時(shí)器的抽象數(shù)據(jù)類型：
public class StopWatch{
private final long start;
public StopWatch(){
start = System.currentTimeMillis();
}
public double elapsedTime(){
long now = System.currentTimeMillis();
return (now - start) / 1000.0;
}
}
數(shù)學(xué)模型
程序運(yùn)行總時(shí)間主要和兩點(diǎn)有關(guān)：
- 執(zhí)行每條語(yǔ)句的耗時(shí)（取決于計(jì)算機(jī)、Java編譯器和操作系統(tǒng)）
- 執(zhí)行每條語(yǔ)句的頻率（取決于程序本身和輸入）
對(duì)于執(zhí)行頻率，有些分析很容易，如在 Three.count() 中將 cnt 設(shè)為 0 的語(yǔ)句只會(huì)執(zhí)行一次；有些需要深入分析，如 Three.count() 中的 if 語(yǔ)句會(huì)執(zhí)行 N(N-1)(N-2)/6 次。
近似
用 ~f(N) 表示所有隨著N增大除以f(N)的結(jié)果趨近于1的函數(shù)。用g(N)~f(N)表示隨著g(N)/f(N) 隨著N增大趨近于1。
一般用到的近似方式都是g(N)~f(N)，其中 f(N)=Nb(logN)c，其中a,b和c均為常數(shù)，將f(N)稱為g(N)的增長(zhǎng)數(shù)量級(jí)。
常見的增長(zhǎng)數(shù)量級(jí)函數(shù):
| 描述 | 函數(shù) B |
|---|---|
| 常數(shù)級(jí) | 1 |
| 對(duì)數(shù)級(jí) | logN |
| 線性級(jí) | N |
| 線性對(duì)數(shù)級(jí) | NlogN |
| 平方級(jí) | N^2 |
| 立方級(jí) | N^3 |
| 指數(shù)級(jí) | 2^N |
執(zhí)行最頻繁的執(zhí)行決定了程序執(zhí)行的總時(shí)間——稱這些指令為程序的內(nèi)循環(huán)
成本模型
用成本模型來(lái)評(píng)估算法的性質(zhì)，這個(gè)模型定義了所研究算法中的基本操作。例如，3-Sum問(wèn)題的成本模型是訪問(wèn)數(shù)組元素的次數(shù)。
構(gòu)建運(yùn)行時(shí)間的數(shù)學(xué)模型所需步驟：
- 確定輸入模型，定義問(wèn)題規(guī)模
- 識(shí)別內(nèi)循環(huán)
- 根據(jù)內(nèi)循環(huán)中的操作確定成本模型
- 對(duì)給定輸入，判斷這些操作的執(zhí)行頻率
如二分查找，它的輸入模型是大小為N的數(shù)組a[]，內(nèi)循環(huán)是while循環(huán)中所有語(yǔ)句，成本模型是比較操作（比較兩個(gè)數(shù)組元素的值）
設(shè)計(jì)更快的算法
2-Sum 問(wèn)題
假設(shè)所有整數(shù)各不相同，這個(gè)問(wèn)題很容易在平方級(jí)別——雙重循環(huán)來(lái)解決，下面利用歸并排序和二分查找在線性對(duì)數(shù)級(jí)別解決 2-Sum 問(wèn)題：
思路：當(dāng)且僅當(dāng) -a[i] 存在于數(shù)組中（且a[i]非0）時(shí)，a[i] 存在于某個(gè)和為0的整數(shù)對(duì)中。
public class TwoSumFast{
public static int count(int[] a){
//先排序
Arrays.sort(a);
int cnt = 0;
for(int i = 0; i < a.length; i++){
if(BinarySearch.rank(-a[i], a) > i)
cnt++;
}
return cnt;
}
}
歸并排序所需時(shí)間與NlogN成正比，二分查找所需時(shí)間和logN成正比，因此整個(gè)算法運(yùn)行時(shí)間和NlogN成正比。
3-Sum 問(wèn)題
同樣假設(shè)所有整數(shù)各不相同，同上面一樣，當(dāng)且僅當(dāng) -(a[i] + a[j]) 在數(shù)組中（不是a[i] 也不是 a[j]）時(shí)，整數(shù)對(duì)（a[i] 和 a[j]）為某個(gè)和為0的三元組的一部分。
public class ThreeSumFast{
public static int count(int[] a){
//先排序
Arrays.sort(a);
int cnt = 0;
for(int i = 0; i < a.length; i++){
for(int j = i + 1; j < a.length; j++)
if(BinarySearch.rank(-(a[i] + a[j]), a) > j)
cnt++;
}
return cnt;
}
}
內(nèi)存
對(duì)象
數(shù)組
字符串對(duì)象
當(dāng)調(diào)用substring()方法時(shí)，就創(chuàng)建了一個(gè)新的String對(duì)象（40字節(jié)），但仍然重用了相同的value[]數(shù)組，因此該字符串的子字符串只會(huì)使用40字節(jié)的內(nèi)存，也就是說(shuō)，一個(gè)子字符串的額外內(nèi)存是一個(gè)常數(shù)，構(gòu)造一個(gè)子字符串所需時(shí)間也是常數(shù)。
舉例：union-find 算法
動(dòng)態(tài)連通性
問(wèn)題的輸入是一列整數(shù)對(duì)，其中每個(gè)整數(shù)都表示一個(gè)某種類型的對(duì)象，一對(duì)整數(shù)p q可以被理解為“p和q是相連的”，具有如下性質(zhì)；
- 自反性：p和p是
- 對(duì)稱性：若p和q相連，則q和p也相連
- 傳遞性：若p和q相連且q和r相連，則p和r也相連
union-find 算法API
| 方法名 | 操作 |
|---|---|
| UF(int N) | 以整數(shù)標(biāo)識(shí)（0到N-1）初始化N個(gè)觸點(diǎn) |
| void union(int p, int q) | 在p和q之間添加一條連接 |
| int find(int p) | p所在的分量的標(biāo)識(shí)符（0到N-1） |
| boolean connected(int p, int q) | 如果p和q存在于同一個(gè)分量則返回true |
| int count() | 連通分量的數(shù)量 |
用一個(gè)以觸點(diǎn)為索引的數(shù)組id[]作為基本數(shù)據(jù)結(jié)構(gòu)來(lái)表示所有分量。初始有N個(gè)分量，每個(gè)觸點(diǎn)都構(gòu)成了一個(gè)只含有它自己的分量，因此將id[i]初始化為i，其中i為0到N-1。find()判定它所在分量所需的信息保存在id[i]之中。connected()方法只有一條語(yǔ)句find(p)==find(q)，它返回一個(gè)布爾值。
實(shí)現(xiàn)
1 quick-find 算法
代碼
public class UF{
private int[] id;
private int count;
public UF(int N){
id = new int[N];
count = N;
for(int i = 0; i < N; i++){
id[i] = i;
}
}
public void union(int p, int q){
int pid = find(p);
int qid = find(q);
if(pid == qid){
return;
}
for(int i = 0; i < id.length; i++){
if(id[i] == pid){
id[i] = qid;
}
}
count--;
}
public int find(int p){
return id[p];
}
public boolean connected(int p, int q){
return id[p] == id[q];
}
public int count(){
return count;
}
}
分析
上述代碼的find方法十分高效，因?yàn)閮H僅需要一次數(shù)組讀取操作就能夠找到該節(jié)點(diǎn)的組號(hào)，但是問(wèn)題隨之而來(lái)，對(duì)于需要添加新路徑的情況，就涉及到對(duì)于組號(hào)的修改，因?yàn)椴⒉荒艽_定哪些節(jié)點(diǎn)的組號(hào)需要被修改，因此就必須對(duì)整個(gè)數(shù)組進(jìn)行遍歷，找到需要修改的節(jié)點(diǎn)，逐一修改，每次添加新路徑帶來(lái)的復(fù)雜度就是線性關(guān)系了，如果要添加的新路徑的數(shù)量是M，節(jié)點(diǎn)數(shù)量是N，那么最后的時(shí)間復(fù)雜度就是MN，顯然是一個(gè)平方階的復(fù)雜度，對(duì)于大規(guī)模的數(shù)據(jù)而言，平方階的算法是存在問(wèn)題的，這種情況下，每次添加新路徑就是“牽一發(fā)而動(dòng)全身”，想要解決這個(gè)問(wèn)題，關(guān)鍵就是要提高union方法的效率，讓它不再需要遍歷整個(gè)數(shù)組。
2 quick-union 算法
代碼
id[] 數(shù)組用父鏈接的形式表示了一片森林，從任何觸點(diǎn)所對(duì)應(yīng)的節(jié)點(diǎn)開始跟隨鏈接，最終都將到達(dá)含有該節(jié)點(diǎn)的樹的根節(jié)點(diǎn)。quick-union 中 union() 的實(shí)現(xiàn)只用了一條語(yǔ)句就將一個(gè)根節(jié)點(diǎn)變?yōu)榱硪粋€(gè)根節(jié)點(diǎn)的父節(jié)點(diǎn)，從而歸并了兩棵樹。
public class QuickUnionUF{
private int[] id;
private int count;
public QuickUnionUF(int N){
id = new int[N];
count = N;
for(int i = 0; i < N; i++){
id[i] = i;
}
}
public void union(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot){
return;
}
id[pRoot] = qRoot;
count--;
}
public int find(int p){
while(p != id[p]){
p = id[p];
}
return p;
}
public boolean connected(int p, int q){
return find(p) == find(q);
}
public int count(){
return count;
}
}
分析
quick-union 算法看起來(lái)比 quick-find 算法更快，因?yàn)樗恍枰獮槊繉?duì)輸入遍歷整個(gè)數(shù)組。但樹這種數(shù)據(jù)結(jié)構(gòu)容易出現(xiàn)極端情況，因?yàn)樵诮涞倪^(guò)程中，樹的最終形態(tài)嚴(yán)重依賴于輸入數(shù)據(jù)本身的性質(zhì)，比如數(shù)據(jù)是否排序，是否隨機(jī)分布等等。比如在輸入數(shù)據(jù)是有序的情況下，構(gòu)造的BST會(huì)退化成一個(gè)鏈表。如下圖所示。
定義：一棵樹的大小是它的節(jié)點(diǎn)的數(shù)量。樹中一個(gè)節(jié)點(diǎn)的深度是它到根節(jié)點(diǎn)的路徑上的鏈接（也就是邊）數(shù)。樹的高度是它的所有節(jié)點(diǎn)中的最大深度。
命題：quick-union 算法中 find() 方法訪問(wèn)數(shù)組的次數(shù)為1加上給定觸點(diǎn)所對(duì)應(yīng)的節(jié)點(diǎn)的深度的兩倍。union() 和 connected() 訪問(wèn)數(shù)組的次數(shù)為兩次find() 操作（若union()中給定的兩個(gè)觸點(diǎn)分別存在于不同的樹中則還需要加1）。
由命題G可知，對(duì)于整數(shù)對(duì)0 i，union()操作訪問(wèn)數(shù)組的次數(shù)為2i+2（觸點(diǎn)0的深度為i，觸點(diǎn)i的深度為0）。因此，處理N對(duì)整數(shù)所需的所有find()操作訪問(wèn)數(shù)組的總次數(shù)為2(1+2+...+N)~N^2。
3 加權(quán) quick-union 算法
只需簡(jiǎn)單修改quick-union算法就能保證像這樣的最壞情況不會(huì)出現(xiàn)。與其在 union() 中隨意將一棵樹連接到另一棵樹，現(xiàn)在記錄每棵樹的大小并總是將較小的樹連接到大數(shù)上。此時(shí)需添加一個(gè)數(shù)組來(lái)記錄樹中節(jié)點(diǎn)數(shù)，將這種算法稱為加權(quán) quick-union 算法。該算法構(gòu)造的樹的高度也遠(yuǎn)遠(yuǎn)小于未加權(quán)版本構(gòu)造的樹的高度。
代碼
public class WeightedUnionUF{
private int[] id;
private int count;
private int[] sz;
public WeightedUnionUF(int N){
id = new int[N];
count = N;
for(int i = 0; i < N; i++){
id[i] = i;
sz[i] = 1;
}
}
public void union(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot){
return;
}
//比較樹大小，小樹指向大樹，修改大樹大小
if(sz[pRoot] < sz[qRoot]){
id[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}else{
id[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
count--;
}
public int find(int p){
while(p != id[p]){
p = id[p];
}
return p;
}
public boolean connected(int p, int q){
return find(p) == find(q) ;
}
public int count(){
return count;
}
}
分析
命題H：對(duì)于N個(gè)觸點(diǎn)，加權(quán)quick-union算法夠早的森林中的任意節(jié)點(diǎn)的深度最多為lgN。
推論：對(duì)于加權(quán)quick-union算法和N個(gè)觸點(diǎn)，在最壞情況下find()、connected()和union()的成本增長(zhǎng)數(shù)量級(jí)為logN。
命題H和推論的意義在于加權(quán)quick-union算法是三種算法中唯一可以用于解決大型實(shí)際問(wèn)題的算法。加權(quán)quick-union算法處理N個(gè)觸點(diǎn)和M條連接時(shí)最多訪問(wèn)數(shù)組cMlgN次，c為常數(shù)，比quick-find（和某些情況下的quick-union）需要訪問(wèn)數(shù)組至少M(fèi)N次形成鮮明對(duì)比。
4 最優(yōu)算法——基于quick-union 算法進(jìn)行路徑壓縮
理想情況下，我們希望每個(gè)結(jié)點(diǎn)都直接鏈接到它的根節(jié)點(diǎn)，但又不想像quick-find那樣通過(guò)修改大量鏈接實(shí)現(xiàn)，實(shí)際實(shí)現(xiàn)很簡(jiǎn)單——在檢查節(jié)點(diǎn)時(shí)將它們直連到根節(jié)點(diǎn)。
public int find(int p){
while(p != id[p]){
//若當(dāng)前節(jié)點(diǎn)非根節(jié)點(diǎn)
//則使當(dāng)前節(jié)點(diǎn)指向父節(jié)點(diǎn)的父節(jié)點(diǎn)/或直接指向根節(jié)點(diǎn)find(index)
id[p] = id[id[p]];
p = id[p];
}
return p;
}
所得到的結(jié)果幾乎是完全扁平化的樹，即路徑壓縮的加權(quán)quick-union算法是最優(yōu)的算法
