建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

本章內(nèi)容頗多，所以我分三篇來寫，這一篇是關(guān)于一些基本的概念和選擇，后面兩篇分別是插入和刪除。

上一章總結(jié)過BST(http://www.wutianqi.com/?p=2430)，BST在高度較小時(shí)，可以獲得很好的性能(因?yàn)锽ST的操作的平均時(shí)間為O(lgn))，但是在高度較大時(shí)，則性能就一般。而紅黑樹“近似平衡”，于是降低了平均時(shí)間，再者，紅黑樹并不追求“完全平衡”——它只要求部分地達(dá)到平衡要求，降低了對旋轉(zhuǎn)的要求，從而提高了性能。

談到紅黑樹的用途，最廣為人知的應(yīng)該就是紅黑樹在C++ STL中的應(yīng)用了，在set, multiset, map, multimap等中，都應(yīng)用了紅黑樹(具體大家可以去網(wǎng)上搜搜)。

 

下面給出紅黑樹和黑高度的定義：

滿足下面幾個(gè)條件(紅黑性質(zhì))的二叉搜索樹，稱為紅黑樹：
1. 每個(gè)結(jié)點(diǎn)或是紅色，或是是黑色。
2. 根結(jié)點(diǎn)是黑的。
3. 所有的葉結(jié)點(diǎn)(NULL)是黑色的。（NULL被視為一個(gè)哨兵結(jié)點(diǎn)，所有應(yīng)該指向NULL的指針，都看成指向了NULL結(jié)點(diǎn)。）
4. 如果一個(gè)結(jié)點(diǎn)是紅色的，則它的兩個(gè)兒子節(jié)點(diǎn)都是黑色的。
5. 對每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其子孫結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)。

黑高度的定義：
從某個(gè)結(jié)點(diǎn)出發(fā)(不包括該結(jié)點(diǎn))到達(dá)一個(gè)葉結(jié)點(diǎn)的任意一條路徑上，黑色結(jié)點(diǎn)的個(gè)數(shù)成為該結(jié)點(diǎn)x的黑高度。

下面就是一個(gè)紅黑樹：

紅黑樹是二叉搜索樹的一種。它與普通二叉搜索樹不同的是，紅黑樹的每個(gè)節(jié)點(diǎn)都附加了另一個(gè)屬性――顏色，可以是紅色，也可以是黑色。通過對于每條路徑上節(jié)點(diǎn)顏色的規(guī)則進(jìn)行限定，紅黑樹可以保證任何兩條從根部到樹葉的路徑節(jié)點(diǎn)個(gè)數(shù)相差不超過2倍。所以，紅黑樹是一種近似平衡的二叉搜索樹。

紅黑樹的查找、最大值、最小值、前趨、后繼等操作，與普通的二叉搜索樹沒有什么區(qū)別。插入和刪除操作需要重新實(shí)現(xiàn)。僅僅用普通的二叉搜索樹的插入和刪除動(dòng)作，可能會(huì)破壞紅黑樹本身的一些性質(zhì)，因此，需要進(jìn)行額外的處理。這些額外的處理主要是改變樹節(jié)點(diǎn)的顏色，或是改變樹的結(jié)構(gòu)。

關(guān)于旋轉(zhuǎn)：

我把13-2手動(dòng)畫了一次并添加了一些注釋：

 

旋轉(zhuǎn)其實(shí)比較簡單，就不多說了，以下是代碼：

 

下一篇是關(guān)于插入。

 

在我獨(dú)立博客上的原文：http://www.wutianqi.com/?p=2438

歡迎大家互相學(xué)習(xí)，互相討論！

     摘要: 建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html 推薦在看算法導(dǎo)論的這一章之前先看看嚴(yán)蔚敏老師在《數(shù)據(jù)結(jié)構(gòu)》上的二叉查找樹。 整體來說二叉查找樹不難，就是插入和刪除節(jié)點(diǎn)時(shí)讓人糾結(jié)，我就是在刪除節(jié)點(diǎn)時(shí)各種糾結(jié)了。 二叉樹執(zhí)行基本操作的時(shí)間與樹的高度成正比。 首先說下二叉查找樹的性質(zhì)： 設(shè)x為二叉查...  閱讀全文

建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

 

第10章沒法說，數(shù)據(jù)結(jié)構(gòu)還是看嚴(yán)奶奶的比較好，所以《算法導(dǎo)論》上的這一章我隨便瞄了幾眼就過去了，不過話說回來，數(shù)據(jù)結(jié)構(gòu)非常重要?。。∷?，大家最好把嚴(yán)蔚敏的《數(shù)據(jù)結(jié)構(gòu)》認(rèn)認(rèn)真真的看N遍?。。?/p>

另外，推薦看看這個(gè)：

數(shù)據(jù)結(jié)構(gòu)的源碼實(shí)現(xiàn)：http://www.cppleyuan.com/viewthread.php?tid=418

 

第11章散列表也屬于數(shù)據(jù)結(jié)構(gòu)方面的知識(shí)，第10章只是講了最基本的幾個(gè)結(jié)構(gòu)。這一章也很簡單，其實(shí)就是介紹了一些概念及思想，很容易理解。(你可以把散列表想象成平時(shí)用的英語字典，26個(gè)英文字母就是下標(biāo)，通過它來定位你要查的單詞。)

所以這一章我就不重復(fù)去打出概念了，我把幾個(gè)散列函數(shù)和處理碰撞的方法放在圖表里方便對比。

 

①.散列表的優(yōu)點(diǎn)：出色的期望性能。

②.引出：

直接尋址表(P132)的缺點(diǎn)：

1.全域U也許會(huì)很大。

2.實(shí)際關(guān)鍵字域K也許相對于U會(huì)很小。

由此引出了散列表。

以下是我總結(jié)對比的表：

 

這一章我也不知道該怎么說，表面上感覺比較簡單，但是如果深入研究，會(huì)發(fā)現(xiàn)它的內(nèi)容太多了，而且很好很強(qiáng)大。所以還是建議大家看看書也許以后深入了解了我會(huì)再補(bǔ)充。

這幾天主要在研究紅黑樹在，那個(gè)暈啊，不過總算弄明白了，心情也跟著很爽，接下來的一些章節(jié)都比較麻煩了，大家一起加油！

在我獨(dú)立博客上的原文：http://www.wutianqi.com/?p=2419

歡迎大家互相學(xué)習(xí)，互相討論！

建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

這一章的內(nèi)容很簡單，基本都是一些概念。

第i個(gè)順序統(tǒng)計(jì)量:在一個(gè)由n個(gè)元素組成的集合中，第i個(gè)順序統(tǒng)計(jì)量(order statistic)是該集合中第i小的元素。

最小值是第1個(gè)順序統(tǒng)計(jì)量(i=1)

最大值是第n個(gè)順序統(tǒng)計(jì)量(i=n)

中位數(shù)：一個(gè)中位數(shù)(median)是它所在集合的“中點(diǎn)元素”，當(dāng)n為奇數(shù)時(shí)，i=(n+1)/2，當(dāng)n為偶數(shù)是，中位數(shù)總是出現(xiàn)在 （下中位數(shù)）和 （上中位數(shù)）。

找最大值/最小值問題，通過比較n-1次可以得出結(jié)果。

MINIMUM(A)
1  min ← A[1]
2  for i ← 2 to length[A]
3         do if min > A[i]
4                then min ← A[i]
5  return min

如果要同時(shí)找出最大值和最小值，則比較次數(shù)最少并不是2*n-2，而是 ，我們可以將一對元素比較，然后把較大者于max比較，較小者與min比較，這樣就只需要 。

如果是一般的選擇問題，即找出一段序列第i小的數(shù)，看起來要比找最大值或最小值要麻煩，其實(shí)兩種問題的漸進(jìn)時(shí)間都是 。

首先看看這個(gè)強(qiáng)悍的偽代碼：

RANDOMIZED-SELECT(A, p, r, i)
1  if p = r
2      then return A[p]
3  q ← RANDOMIZED-PARTITION(A, p, r)
4  k ← q - p + 1
5  if i = k          ? the pivot value is the answer
6      then return A[q]
7  elseif i < k
8      then return RANDOMIZED-SELECT(A, p, q - 1, i)
9  else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

這個(gè)算法利用了隨機(jī)化的Partition算法，這個(gè)實(shí)在第七章的隨機(jī)化快排中講到：http://www.wutianqi.com/?p=2368，不記得的可以先復(fù)習(xí)下前面的快排。

這個(gè)隨機(jī)化的選擇算法返回?cái)?shù)組A[p..r]中第i小的元素。

具體實(shí)現(xiàn)如下：

結(jié)果如圖：

在(89, 100, 21, 5, 2, 8, 33, 27, 63)中查找第二小的數(shù)字是5. 

該算法的平均情況性能較好，并且又是隨機(jī)化的，所有沒有哪一種特別的輸入會(huì)導(dǎo)致最壞情況發(fā)生。

在我獨(dú)立博客上的原文：http://www.wutianqi.com/?p=2395
歡迎大家互相學(xué)習(xí)，互相探討。      摘要: 建議先看看前言 ： http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html 這一節(jié)講的是非線性排序。 一.計(jì)數(shù)排序(Counting Sort) 基本思想：對每一個(gè)輸入元素x，確定出小于x的元素個(gè)數(shù)。 適用范圍：適用于輸入是由小范圍的整數(shù)構(gòu)成的序列。 穩(wěn)定性：算法是穩(wěn)定的。 具體實(shí)現(xiàn)：  1 ...  閱讀全文

建議先看看前言 ： http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

 

第八章將介紹幾種非比較排序—計(jì)數(shù)排序，基數(shù)排序，桶排序，這三種排序都在線性時(shí)間下運(yùn)行的。

這一節(jié)決策樹其實(shí)是對前面的堆排序，快排等是最優(yōu)的比較算法的證明，

首先說下《算法導(dǎo)論》上對決策樹的定義：一棵決策樹是一棵滿二叉樹(注意看下面解釋)，表示某排序算法作用于給定輸入所做的所有比較，而控制結(jié)構(gòu)，移動(dòng)等都被忽略了。

注意：這里個(gè)人認(rèn)為定義是錯(cuò)誤的，決策樹不是一棵滿二叉樹，連完全二叉樹都不是。(不知道有沒有朋友看到這里和我想法一樣？)

首先看看只有三個(gè)元素時(shí)，決策樹的圖：

在決策樹中，每個(gè)內(nèi)結(jié)點(diǎn)都用i:j表示比較下標(biāo)為i數(shù)組元素與下標(biāo)為j的數(shù)組元素的大小。每一個(gè)葉結(jié)點(diǎn)是一個(gè)n個(gè)元素的全排列。

所以排序算法的執(zhí)行對應(yīng)于遍歷一條從樹的根到葉結(jié)點(diǎn)的路徑！

因?yàn)橛衝個(gè)結(jié)點(diǎn)，根據(jù)高中學(xué)的組合排列知識(shí)，知道有n!個(gè)情況，也就是n!個(gè)葉子結(jié)點(diǎn)。

在決策樹中，從根到任意一個(gè)可達(dá)葉結(jié)點(diǎn)之間的最長路徑的長度，表示對應(yīng)的排序算法中最壞情況下的比較次數(shù)。這樣，一個(gè)比較算法的最壞情況的比較次數(shù)就是其決策樹的高度。

定理8.1證明了任意一個(gè)比較算法在最壞情況下都需要做?(n lg n)次的比較。這個(gè)證明比較簡單，可以看看書上的證明過程。

這一節(jié)其實(shí)沒什么內(nèi)容，就是一點(diǎn)基本的概念，以及了解比較算法可以通過轉(zhuǎn)換為決策樹這個(gè)模型去理解。

 

推薦先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

其實(shí)這一篇我老早就寫過了，只不過最近在總結(jié)《算法導(dǎo)論》，而第七章就是快速排序，我當(dāng)初總結(jié)的快排也是根據(jù)算法導(dǎo)論來的，為了方便大家閱讀，我在這里把曾經(jīng)寫過的重新再貼一遍。

---

前幾天寫過一個(gè)堆排序的文章(http://www.wutianqi.com/?p=1820)，里面謝了很多講解和代碼注釋，個(gè)人感覺快速排序不是很難，所以不想寫講解，也不需要寫注釋，大家如果不明白什么是快速排序，可以去看下文章最后我推薦的幾個(gè)鏈接。

 

我查過網(wǎng)上很多關(guān)于快排的文章和代碼，但是基本都是最原始的快排，即霍爾(Hoare)快排。想必大家也沒有注意這些，我準(zhǔn)備把霍爾快排，算法導(dǎo)論上的快排和隨機(jī)化快排的代碼一起發(fā)出來，供大家對比與學(xué)習(xí)，歡迎大家和我探討

代碼一.霍爾快排：

/*
 * Author: Tanky Woo
 * Blog:   www.WuTianQi.com
 * Note:   快速排序版本1 --- Hoare-Partition
 */
 
#include <iostream>
using namespace std;
 
int num;
 
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
 
void PrintArray(int *arr)
{
    for(int i=1; i<=num; ++i)
        cout << arr[i] << " ";
    cout << endl;
}
 
int Partition1(int *arr, int beg, int end)
{
    int low = beg, high = end;
    int sentinel = arr[beg];
    while(low < high)
    {
        while(low<high && arr[high]>=sentinel)
            --high;
        arr[low] = arr[high];
        while(low<high && arr[low]<=sentinel)
            ++low;
        arr[high] = arr[low];
    }
    arr[low] = sentinel;
 
    cout << "排序過程:";
    PrintArray(arr);
    return low;
}
 
void QuickSort(int *arr, int beg, int end)
{
    if(beg < end)
    {
        int pivot = Partition1(arr, beg, end);
        QuickSort(arr, beg, pivot-1);
        QuickSort(arr, pivot+1, end);
    }
}
 
int main()
{
    int arr[100];
    cout << "Input the num of the elements:\n";
    cin >> num;
    cout << "Input the elements:\n";
    for(int i=1; i<=num; ++i)
        cin >> arr[i];
    QuickSort(arr, 1, num);
    cout << "最后結(jié)果:";
    PrintArray(arr);
    return 0;
}

代碼二.《算法導(dǎo)論》里講的快排：

/*
 * Author: Tanky Woo
 * Blog:   www.WuTianQi.com
 * Note:   快速排序版本2---《算法導(dǎo)論》
 */
 
#include <iostream>
using namespace std;
 
int num;
 
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
 
void PrintArray(int *arr)
{
    for(int i=1; i<=num; ++i)
        cout << arr[i] << " ";
    cout << endl;
}
 
int Partition2(int *arr, int beg, int end)
{
    int sentinel = arr[end];
    int i = beg-1;
    for(int j=beg; j<=end-1; ++j)
    {
        if(arr[j] <= sentinel)
        {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[end]);
 
    cout << "排序過程:";
    PrintArray(arr);
    return i+1;
}
 
void QuickSort(int *arr, int beg, int end)
{
    if(beg < end)
    {
        int pivot = Partition2(arr, beg, end);
        QuickSort(arr, beg, pivot-1);
        QuickSort(arr, pivot+1, end);
    }
}
 
int main()
{
    int arr[100];
    cout << "Input the num of the elements:\n";
    cin >> num;
    cout << "Input the elements:\n";
    for(int i=1; i<=num; ++i)
        cin >> arr[i];
    QuickSort(arr, 1, num);
    cout << "最后結(jié)果:";
    PrintArray(arr);
    return 0;
}

代碼三.隨機(jī)快排：

/*
 * Author: Tanky Woo
 * Blog:   www.WuTianQi.com
 * Note:   快速排序版本3 --- 隨機(jī)化版本
 * 解決待排序元素相差很大的情況
 */
 
 
#include <iostream>
#include <cstdlib>
using namespace std;
 
int num;
 
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
 
void PrintArray(int *arr)
{
    for(int i=1; i<=num; ++i)
        cout << arr[i] << " ";
    cout << endl;
}
 
int Partition3(int *arr, int beg, int end)
{
    int sentinel = arr[end];
    int i = beg-1;
    for(int j=beg; j<=end-1; ++j)
    {
        if(arr[j] <= sentinel)
        {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[end]);
 
    cout << "排序過程:";
    PrintArray(arr);
    return i+1;
}
 
int RandomPartition(int *arr, int beg, int end)
{
    int i = beg + rand() % (end-beg+1);
    swap(arr[i], arr[end]);
    return Partition3(arr, beg, end);
}
 
 
void RandomQuickSort(int *arr, int beg, int end)
{
    if(beg < end)
    {
        int pivot = RandomPartition(arr, beg, end);
        RandomQuickSort(arr, beg, pivot-1);
        RandomQuickSort(arr, pivot+1, end);
    }
}
 
int main()
{
    int arr[100];
    cout << "Input the num of the elements:\n";
    cin >> num;
    cout << "Input the elements:\n";
    for(int i=1; i<=num; ++i)
        cin >> arr[i];
    RandomQuickSort(arr, 1, num);
    cout << "最后結(jié)果:";
    PrintArray(arr);
    return 0;
}

最后，我想說下，隨機(jī)化的快排一般適用于待排序的數(shù)據(jù)之間相差較大的情況下。

這里給出幾篇網(wǎng)上講得不錯(cuò)的文章：

1.http://bbs.chinaunix.net/viewthread.php?tid=1011316

算是一個(gè)討論帖。很給力！

2.http://www.javaeye.com/topic/561718

講得比較詳細(xì)，不過代碼是Java的。

3.http://tayoto.blog.hexun.com/25048556_d.html

4.http://www.360doc.com/content/10/1106/11/1317564_67067368.shtml

概念上很詳細(xì)。

5.http://blog.csdn.net/wssxy/archive/2008/12/05/3448642.aspx

一篇講快排的佳作！

6.http://www.cnblogs.com/chinazhangjie/archive/2010/12/09/1901491.html

小杰的文章，用C++模板類寫的。大家可以去學(xué)習(xí)學(xué)習(xí)。

在我獨(dú)立博客上的原文：http://www.wutianqi.com/?p=2368
歡迎大家互相學(xué)習(xí)，互相探討。

建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

上一章總結(jié)是的堆排序算法，這一章同樣是利用了堆這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)在是優(yōu)先級(jí)隊(duì)列。

根據(jù)堆分為最大堆，最小堆，所以優(yōu)先級(jí)隊(duì)列也可以分為最大優(yōu)先級(jí)隊(duì)列和最小優(yōu)先級(jí)隊(duì)列。

優(yōu)先級(jí)隊(duì)列的概念和用途書上已經(jīng)寫的很清楚了，我就不再打一遍了。直接寫出具體實(shí)現(xiàn)。

在實(shí)現(xiàn)前先說幾點(diǎn)：

1.上一章說過，堆的length和heapsize要區(qū)分清楚，這一章的優(yōu)先級(jí)隊(duì)列里就用到了。

2.優(yōu)先級(jí)隊(duì)列用到了上一章的一些函數(shù)比如MaxHeapify()，不記得的可以復(fù)習(xí)下上一章。

以下是代碼及講解(此處實(shí)現(xiàn)的是最大優(yōu)先級(jí)隊(duì)列)：

以下是運(yùn)行結(jié)果：

看上圖的結(jié)果：

在第二次使用HeapExtractMax后，把第二個(gè)數(shù)字即6設(shè)為15，更新后，結(jié)果就是HeapIncreaseKey的輸出。

建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

首先介紹幾個(gè)概念：

衛(wèi)星數(shù)據(jù)：一個(gè)帶排序的的數(shù)通常是有一個(gè)稱為記錄的數(shù)據(jù)集組成的，每一個(gè)記錄有一個(gè)關(guān)鍵字key，記錄的其他數(shù)據(jù)稱為衛(wèi)星數(shù)據(jù)。

原地排序：在排序輸入數(shù)組時(shí)，只有常數(shù)個(gè)元素被存放到數(shù)組以外的空間中去。

 

在第二章介紹了兩種排序：插入排序和合并排序，接下來兩章要介紹的是推排序和快速排序，這四個(gè)排序都屬于比較排序(comparison sort)。

 

我以前總結(jié)過堆排序，并具體實(shí)現(xiàn)了堆排序，代碼中給出了詳細(xì)的注釋，所以在這里就不重復(fù)發(fā)了，大家可以去看看，個(gè)人覺得總結(jié)的還是比較給力的：

http://www.wutianqi.com/?p=1820

這里再補(bǔ)充幾點(diǎn)：

1.區(qū)別length[A]和heap-sort[A]。(P73)(這個(gè)在下一篇的優(yōu)先級(jí)隊(duì)列中將會(huì)具體區(qū)別)

2.總體上看堆排序由三個(gè)函數(shù)組成：①.MAX-HEAPIFY ②.BUILD-MAX-HEAP ③.HEAP-SORT

 

另外，在這里給大家補(bǔ)充一點(diǎn)個(gè)人經(jīng)驗(yàn)，有時(shí)理論難以理解，代碼難以理解，這個(gè)時(shí)候，就要靠秘訣了：拿起手中的筆和紙，自己給出一組輸入，按照書上的代碼，自己去模擬這組輸入的執(zhí)行過程。(這個(gè)過程人人都知道，但并不是人人都去做了！學(xué)算法，就要自己去模擬，去畫圖，去推！怎么樣容易理解就怎么去做！)

所以這也是我喜歡《算法導(dǎo)論》的原因，接下來，就要強(qiáng)烈推薦大家看《算法導(dǎo)論》上非常非常給力的堆排序?qū)崿F(xiàn)圖了—圖6-4。

 

 

總結(jié)：本章最基礎(chǔ)也是最重要的就是理解堆這種結(jié)構(gòu)！

堆是什么？來看看《算法導(dǎo)論》上的圖6-1：

圖(a)是一個(gè)最大堆，圖(b)是最大堆的數(shù)組表示。可以看到堆的數(shù)組并不是已排序好的。

讓我們來回憶下最大堆的定義(P74)：

在最大堆中，最大堆特性是指除了根以外的每個(gè)結(jié)點(diǎn)i，有A[PARENT(i)] >= A[i]。這樣，堆的最大元素就存放在根結(jié)點(diǎn)中。

對，堆排序就是利用的這個(gè)特性—“堆的最大元素就存放在根結(jié)點(diǎn)中”

每次堆化，這樣就找到了當(dāng)前堆的最大元素。

所以說，理解了其本質(zhì)特征，堆排序其實(shí)很簡單的。

至于堆排序的具體應(yīng)用，在后面的最短路算法—Dijkstra中，會(huì)用到由堆來優(yōu)化普通的Dijkstra算法。

下一篇將實(shí)現(xiàn)最大優(yōu)先級(jí)隊(duì)列。

建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/10/143850.html#143880

因?yàn)椤端惴▽?dǎo)論》第一部分1~5章的理論性太強(qiáng)，研究過多容易糾結(jié)，所以索性合起來快點(diǎn)講過去。

第四章：

這一章講的是遞歸式(recurrence)，遞歸式是一組等式或不等式，它所描述的函數(shù)是用在更小的輸入下該函數(shù)的值來定義的。

本章講了三種方法來解遞歸式，分別是代換法，遞歸樹方法，主方法。

1.代換法(Substitution method)(P38~P40)

定義：即在歸納假設(shè)時(shí)，用所猜測的值去代替函數(shù)的解。

用途：確定一個(gè)遞歸式的上界或下界。

缺點(diǎn)：只能用于解的形式很容易猜的情形。

總結(jié)：這種方法需要經(jīng)驗(yàn)的積累，可以通過轉(zhuǎn)換為先前見過的類似遞歸式來求解。

2.遞歸樹方法(Recursion-tree method)

起因：代換法有時(shí)很難得到一個(gè)正確的好的猜測值。

用途：畫出一個(gè)遞歸樹是一種得到好猜測的直接方法。

分析(重點(diǎn))：在遞歸樹中，每一個(gè)結(jié)點(diǎn)都代表遞歸函數(shù)調(diào)用集合中一個(gè)子問題的代價(jià)。將遞歸樹中每一層內(nèi)的代價(jià)相加得到一個(gè)每層代價(jià)的集合，再將每層的代價(jià)相加得到遞歸式所有層次的總代價(jià)。

總結(jié)：遞歸樹最適合用來產(chǎn)生好的猜測，然后用代換法加以驗(yàn)證。

遞歸樹擴(kuò)展過程：①.第二章2.3.2節(jié)分析分治法時(shí)圖2-5(P21~P22)的構(gòu)造遞歸樹過程；②.第四章P41圖4-1的遞歸樹構(gòu)造過程；這兩個(gè)圖需要好好分析。

3.主方法(Master method)

優(yōu)點(diǎn)：針對形如T(n) = aT(n/b) + f(n)的遞歸式

缺點(diǎn)：并不能解所有形如上式的遞歸式的解。

具體分析：

T(n) = aT(n/b) + f(n)描述了將規(guī)模為n的問題劃分為a個(gè)子問題的算法的運(yùn)行時(shí)間，每個(gè)子問題的規(guī)模為n/b。

在這里可以看到，分治法就相當(dāng)于a=2, b=2, f(n) = O(n).

主方法依賴于主定理：(圖片點(diǎn)擊放大)

圖片可以不清晰，可以看書。

主定理的三種情況，經(jīng)過分析，可以發(fā)現(xiàn)都是把f(n)與 比較。

第一種情況是 更大，第二種情況是 與f(n)相等，第三種情況是f(n)更大。

但是，這三種情況并未完全覆蓋所有可能的f(n)：

第一種情況是f(n)多項(xiàng)式的小于 ，而第三種情況是f(n)多項(xiàng)式的大于 ，即兩者相差的是 。如果兩者相差的不是 ，則無法用主定理來確定界。

比如算法導(dǎo)論P(yáng)44最下面的 就不能用主定理來判斷。

至于主定理的證明，有興趣的可以拿筆在紙上推算，反正我這里是沒看的，畢竟時(shí)間有限，要選擇性的學(xué)習(xí)。

第五章：

本章是圍繞一個(gè)雇傭問題展開的。

問題：有一批參與面試的人，你要一個(gè)個(gè)面試(面試每個(gè)人都要花費(fèi)c1)，如果當(dāng)前面試者比自己的助理能力強(qiáng)，則辭掉當(dāng)前助理的，并把當(dāng)前面試者提拔為助理(雇傭一個(gè)人要花費(fèi)c2)，一直面試完所有人。

這里考慮的是面試所花的money，假設(shè)總共有N人參加面試，有M人被雇傭過，則花費(fèi)O(N*c1 + M*c2)，因?yàn)閰⑴c面試的人員順序是不確定的，所以要花費(fèi)的money也是不確定的(N*c1是確定的，而M是不確定的，所以M*c2也是不確定的）。

首先介紹兩個(gè)概念：

1.概率分析：指在問題的分析中應(yīng)用概率的技術(shù)。

2.隨機(jī)算法：如果一個(gè)算法的行為不只是由輸入決定，同時(shí)也由隨機(jī)數(shù)生成器所產(chǎn)生的數(shù)值決定，則成這個(gè)算法是隨機(jī)的。

書上講的理論性有點(diǎn)強(qiáng)，我這里用自己的話來說下：

首先說下概率分析，因?yàn)榍懊嬷v到過：雇傭所需的花費(fèi)與輸入序列有關(guān)，有N個(gè)面試人員(考慮每個(gè)人的能力不一樣)，則一共有N!中排列情況(即每種排列出現(xiàn)的概率是1/(N!))，于是假設(shè)每種排列花費(fèi)Ti元，則所有供花費(fèi)：

T1/(N!) + T2/(N!) + … + TN/(N!)。

其實(shí)這里可以結(jié)合高中學(xué)的正態(tài)分布來理解，都是講的每種情況出現(xiàn)的概率，思想差不多，所以這里也不需要什么概率論的知識(shí)，都是一些常識(shí)。

順便補(bǔ)充一下：5.2節(jié)的指示器隨機(jī)變量就是用的高中學(xué)的期望，用期望來表示概率。

再說下隨機(jī)算法，對于上面概率分析時(shí)的方法，雖然面試人員的排列是不確定的。但是如果當(dāng)排列確定后，則所需花費(fèi)也就確定了。而對于隨機(jī)算法，就算排列確定，其花費(fèi)也是不確定的。即隨機(jī)發(fā)生在算法上，而不是發(fā)生在輸入分布上。這就是概率分析與隨機(jī)算法之間的區(qū)別。

比如按書上的，可以給每個(gè)人員隨機(jī)生成一個(gè)優(yōu)先級(jí)，或者把每一個(gè)面試人員與其后的面試人員中隨機(jī)一員交換，來產(chǎn)生一個(gè)隨機(jī)的序列。

我以前總結(jié)過一些隨機(jī)算法，有興趣的朋友可以去看看：

1.《隨機(jī)化算法(1) — 隨機(jī)數(shù)》

2.《隨機(jī)化算法(2) — 數(shù)值概率算法》

3.《隨機(jī)化算法(3) — 舍伍德(Sherwood)算法》

4.《隨機(jī)化算法(4) — 拉斯維加斯(Las Vegas)算法》

5.《隨機(jī)化算法(5) — 蒙特卡羅(Monte Carlo)算法》

另外，比如像C/C++中庫函數(shù)rand()就是一個(gè)產(chǎn)生隨機(jī)變量的函數(shù)，但是它并不是真正意義上的隨機(jī)函數(shù)，所以稱之為偽隨機(jī)函數(shù)。因?yàn)楫?dāng)srand(seed)設(shè)置的seed一樣時(shí)，則rand()產(chǎn)生的隨機(jī)數(shù)也一樣，所以通?？梢酝ㄟ^rand(-1)來把當(dāng)前時(shí)間作為種子模擬隨機(jī)函數(shù)。

補(bǔ)充：在第五章的5.4節(jié)給出了幾個(gè)題目及其分析，這幾個(gè)題目都很有趣，不過對于數(shù)學(xué)也相對有一定的要求。其實(shí)可以很簡化的想：概率和期望是互相轉(zhuǎn)化的，這幾題就可以考慮是去求期望的。

我昨天在論壇出了一個(gè)邏輯面試題：一樓到十樓的每層電梯門口都放著一顆鉆石，鉆石大小不一。你乘坐電梯 從一樓到十樓，每層樓電梯門都會(huì)打開一次，只能拿一次鉆石，問怎樣才能拿到最大的一顆？

想必好多人都看過這題，網(wǎng)上的解答多種多項(xiàng)，我覺得此題應(yīng)該考察的是最優(yōu)解問題，按照最優(yōu)解的思路，此題沒有100%的解決方法，只能盡量使其期望更高，也就是概率更大。這一題可以說是數(shù)學(xué)和哲學(xué)的完美結(jié)合，有點(diǎn)像人生，總想得到更多，但又怕后面的都不行，各種糾結(jié)啊。。。

總的來說，第五章說來說去都是一個(gè)期望的問題。