觀察
運(yùn)行時間和輸入本身相對無關(guān)裆赵，主要取決于問題規(guī)模
例：統(tǒng)計文件中三個數(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;
}
}
}
}
}
一種表示計時器的抽象數(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)行總時間主要和兩點有關(guān)：
- 執(zhí)行每條語句的耗時（取決于計算機(jī)抱怔、Java編譯器和操作系統(tǒng)）
- 執(zhí)行每條語句的頻率（取決于程序本身和輸入）
對于執(zhí)行頻率，有些分析很容易拉一，如在 Three.count() 中將 cnt 設(shè)為 0 的語句只會執(zhí)行一次；有些需要深入分析旧乞，如 Three.count() 中的 if 語句會執(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)的增長數(shù)量級除盏。
常見的增長數(shù)量級函數(shù):
| 描述 | 函數(shù) B |
|---|---|
| 常數(shù)級 | 1 |
| 對數(shù)級 | logN |
| 線性級 | N |
| 線性對數(shù)級 | NlogN |
| 平方級 | N^2 |
| 立方級 | N^3 |
| 指數(shù)級 | 2^N |
執(zhí)行最頻繁的執(zhí)行決定了程序執(zhí)行的總時間——稱這些指令為程序的內(nèi)循環(huán)
成本模型
用成本模型來評估算法的性質(zhì)，這個模型定義了所研究算法中的基本操作挫以。例如者蠕，3-Sum問題的成本模型是訪問數(shù)組元素的次數(shù)。
構(gòu)建運(yùn)行時間的數(shù)學(xué)模型所需步驟：
- 確定輸入模型掐松，定義問題規(guī)模
- 識別內(nèi)循環(huán)
- 根據(jù)內(nèi)循環(huán)中的操作確定成本模型
- 對給定輸入蠢棱，判斷這些操作的執(zhí)行頻率
如二分查找锌杀，它的輸入模型是大小為N的數(shù)組a[]，內(nèi)循環(huán)是while循環(huán)中所有語句泻仙，成本模型是比較操作（比較兩個數(shù)組元素的值）
設(shè)計更快的算法
2-Sum 問題
假設(shè)所有整數(shù)各不相同糕再，這個問題很容易在平方級別——雙重循環(huán)來解決，下面利用歸并排序和二分查找在線性對數(shù)級別解決 2-Sum 問題：
思路：當(dāng)且僅當(dāng) -a[i] 存在于數(shù)組中（且a[i]非0）時玉转，a[i] 存在于某個和為0的整數(shù)對中突想。
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;
}
}
歸并排序所需時間與NlogN成正比，二分查找所需時間和logN成正比究抓，因此整個算法運(yùn)行時間和NlogN成正比猾担。
3-Sum 問題
同樣假設(shè)所有整數(shù)各不相同，同上面一樣刺下，當(dāng)且僅當(dāng) -(a[i] + a[j]) 在數(shù)組中（不是a[i] 也不是 a[j]）時绑嘹，整數(shù)對（a[i] 和 a[j]）為某個和為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)存
對象
數(shù)組
字符串對象
當(dāng)調(diào)用substring()方法時橘茉，就創(chuàng)建了一個新的String對象（40字節(jié)）工腋，但仍然重用了相同的value[]數(shù)組，因此該字符串的子字符串只會使用40字節(jié)的內(nèi)存畅卓，也就是說擅腰，一個子字符串的額外內(nèi)存是一個常數(shù)，構(gòu)造一個子字符串所需時間也是常數(shù)翁潘。
舉例：union-find 算法
動態(tài)連通性
問題的輸入是一列整數(shù)對趁冈，其中每個整數(shù)都表示一個某種類型的對象，一對整數(shù)p q可以被理解為“p和q是相連的”拜马，具有如下性質(zhì)渗勘；
- 自反性：p和p是
- 對稱性：若p和q相連，則q和p也相連
- 傳遞性：若p和q相連且q和r相連俩莽，則p和r也相連
union-find 算法API
| 方法名 | 操作 |
|---|---|
| UF(int N) | 以整數(shù)標(biāo)識（0到N-1）初始化N個觸點 |
| void union(int p, int q) | 在p和q之間添加一條連接 |
| int find(int p) | p所在的分量的標(biāo)識符（0到N-1） |
| boolean connected(int p, int q) | 如果p和q存在于同一個分量則返回true |
| int count() | 連通分量的數(shù)量 |
用一個以觸點為索引的數(shù)組id[]作為基本數(shù)據(jù)結(jié)構(gòu)來表示所有分量呀邢。初始有N個分量，每個觸點都構(gòu)成了一個只含有它自己的分量豹绪，因此將id[i]初始化為i，其中i為0到N-1申眼。find()判定它所在分量所需的信息保存在id[i]之中瞒津。connected()方法只有一條語句find(p)==find(q)，它返回一個布爾值括尸。
實現(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方法十分高效巷蚪，因為僅僅需要一次數(shù)組讀取操作就能夠找到該節(jié)點的組號，但是問題隨之而來濒翻，對于需要添加新路徑的情況屁柏，就涉及到對于組號的修改啦膜，因為并不能確定哪些節(jié)點的組號需要被修改，因此就必須對整個數(shù)組進(jìn)行遍歷淌喻，找到需要修改的節(jié)點僧家，逐一修改，每次添加新路徑帶來的復(fù)雜度就是線性關(guān)系了裸删，如果要添加的新路徑的數(shù)量是M八拱，節(jié)點數(shù)量是N，那么最后的時間復(fù)雜度就是MN涯塔，顯然是一個平方階的復(fù)雜度肌稻，對于大規(guī)模的數(shù)據(jù)而言，平方階的算法是存在問題的匕荸，這種情況下爹谭，每次添加新路徑就是“牽一發(fā)而動全身”，想要解決這個問題榛搔，關(guān)鍵就是要提高union方法的效率诺凡，讓它不再需要遍歷整個數(shù)組。
2 quick-union 算法
代碼
id[] 數(shù)組用父鏈接的形式表示了一片森林药薯，從任何觸點所對應(yīng)的節(jié)點開始跟隨鏈接绑洛，最終都將到達(dá)含有該節(jié)點的樹的根節(jié)點。quick-union 中 union() 的實現(xiàn)只用了一條語句就將一個根節(jié)點變?yōu)榱硪粋€根節(jié)點的父節(jié)點童本，從而歸并了兩棵樹真屯。
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 算法看起來比 quick-find 算法更快，因為它不需要為每對輸入遍歷整個數(shù)組穷娱。但樹這種數(shù)據(jù)結(jié)構(gòu)容易出現(xiàn)極端情況绑蔫，因為在建樹的過程中，樹的最終形態(tài)嚴(yán)重依賴于輸入數(shù)據(jù)本身的性質(zhì)泵额，比如數(shù)據(jù)是否排序配深，是否隨機(jī)分布等等。比如在輸入數(shù)據(jù)是有序的情況下嫁盲，構(gòu)造的BST會退化成一個鏈表篓叶。如下圖所示。
定義：一棵樹的大小是它的節(jié)點的數(shù)量羞秤。樹中一個節(jié)點的深度是它到根節(jié)點的路徑上的鏈接（也就是邊）數(shù)缸托。樹的高度是它的所有節(jié)點中的最大深度。
命題：quick-union 算法中 find() 方法訪問數(shù)組的次數(shù)為1加上給定觸點所對應(yīng)的節(jié)點的深度的兩倍瘾蛋。union() 和 connected() 訪問數(shù)組的次數(shù)為兩次find() 操作（若union()中給定的兩個觸點分別存在于不同的樹中則還需要加1）俐镐。
由命題G可知，對于整數(shù)對0 i哺哼，union()操作訪問數(shù)組的次數(shù)為2i+2（觸點0的深度為i佩抹，觸點i的深度為0）叼风。因此，處理N對整數(shù)所需的所有find()操作訪問數(shù)組的總次數(shù)為2(1+2+...+N)~N^2棍苹。
3 加權(quán) quick-union 算法
只需簡單修改quick-union算法就能保證像這樣的最壞情況不會出現(xiàn)无宿。與其在 union() 中隨意將一棵樹連接到另一棵樹，現(xiàn)在記錄每棵樹的大小并總是將較小的樹連接到大數(shù)上廊勃。此時需添加一個數(shù)組來記錄樹中節(jié)點數(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：對于N個觸點冰悠，加權(quán)quick-union算法夠早的森林中的任意節(jié)點的深度最多為lgN堡妒。
推論：對于加權(quán)quick-union算法和N個觸點，在最壞情況下find()溉卓、connected()和union()的成本增長數(shù)量級為logN皮迟。
命題H和推論的意義在于加權(quán)quick-union算法是三種算法中唯一可以用于解決大型實際問題的算法。加權(quán)quick-union算法處理N個觸點和M條連接時最多訪問數(shù)組cMlgN次桑寨，c為常數(shù)伏尼，比quick-find（和某些情況下的quick-union）需要訪問數(shù)組至少M(fèi)N次形成鮮明對比。
4 最優(yōu)算法——基于quick-union 算法進(jìn)行路徑壓縮
理想情況下尉尾，我們希望每個結(jié)點都直接鏈接到它的根節(jié)點爆阶，但又不想像quick-find那樣通過修改大量鏈接實現(xiàn)，實際實現(xiàn)很簡單——在檢查節(jié)點時將它們直連到根節(jié)點沙咏。
public int find(int p){
while(p != id[p]){
//若當(dāng)前節(jié)點非根節(jié)點
//則使當(dāng)前節(jié)點指向父節(jié)點的父節(jié)點/或直接指向根節(jié)點find(index)
id[p] = id[id[p]];
p = id[p];
}
return p;
}
所得到的結(jié)果幾乎是完全扁平化的樹辨图，即路徑壓縮的加權(quán)quick-union算法是最優(yōu)的算法
