查找方法演算法導論

⑴ 演算法導論的作品目錄

目錄（Table of Contents）
前言（Preface）
第一部分（Part I） 基礎（Foundations）
第一章 計算中演算法的角色（The Role of Algorithms in Computing）
第二章 開始（Getting Started）
第三章 函數的增長率（Growth of Functions）
第四章 遞歸（Recurrences）
第五章 概率分析與隨機化演算法（Probabilistic Analysis and Randomized Algorithms）
第二部分（Part II） 排序與順序統計（Sorting and Order Statistics）
第六章 堆排序（Heapsort）
第七章快速排序（Quicksort）
第八章 線性時間中的排序（Sorting in Linear Time）
第九章 中值與順序統計（Medians and Order Statistics）
第三部分（Part III） 數據結構（Data Structures）
第十章 基本的數據結構（Elementary Data Structures）
第十一章 散列表（Hash Tables）
第十二章 二叉查找樹（Binary Search Trees）
第十三章 紅-黑樹（Red-Black Trees）
第十四章 擴充的數據結構（Augmenting Data Structures）
第四部分（Part IV） 高級的設計與分析技術（Advanced Design and Analysis Techniques）
第十五章 動態規劃（Dynamic Programming）
第十六章 貪婪演算法（Greedy Algorithms）
第十七章 分攤分析（Amortized Analysis）
第五部分（Part V） 高級的數據結構（Advanced Data Structures）
第十八章 B-樹（B-Trees）
第十九章 二項式堆（Binomial Heaps）
第二十章 斐波納契堆（Fibonacci Heaps）
第二十一章 不相交集的數據結構（Data Structures for Disjoint Sets）
第六部分（Part VI） 圖演算法（Graph Algorithms）
第二十二章 基本的圖演算法（Elementary Graph Algorithms）
第二十三章 最小生成樹（Minimum Spanning Trees）
第二十四章單源最短路徑（Single-Source Shortest Paths）
第二十五章 全對的最短路徑（All-Pairs Shortest Paths）
第二十六章 最大流（Maximum Flow）
第七部分（Part VII） 精選的主題（Selected Topics）
第二十七章 排序網路（Sorting Networks）
第二十八章矩陣運算（Matrix Operations）
第二十九章 線性規劃（Linear Programming）
第三十章 多項式與快速傅里葉變換（Polynomials and the FFT）
第三十一章 數論演算法（Number-Theoretic Algorithms）
第三十二章 字元串匹配（String Matching）
第三十三章 計算幾何學（Computational Geometry）
第三十四章 NP-完備性（NP-Completeness）
第三十五章 近似演算法（Approximation Algorithms）
第八部分（Part VIII） 附錄：數學背景（Mathematical Background）
附錄A 求和（Summations）
附錄B 集合，等等。（Sets, Etc.）
附錄C 計數與概率（Counting and Probability）
參考文獻（Bibliography）
索引（Index）

⑵ 各種查找演算法的比較

二分法平均查找效率是O(logn)，但是需要數組是排序的。如果沒有排過序，就只好先用O（nlogn)的預處理為它排個序了。而且它的插入比較困難，經常需要移動整個數組，所以動態的情況下比較慢。

哈希查找理想的插入和查找效率是O(1)，但條件是需要找到一個良好的散列函數，使得分配較為平均。另外，哈希表需要較大的空間，至少要比O(n)大幾倍，否則產生沖突的概率很高。

二叉排序樹查找也是O(logn)的，關鍵是插入值時需要做一些處理使得它較為平衡（否則容易出現輕重的不平衡，查找效率最壞會降到O(n)），而且寫起來稍微麻煩一些，具體的演算法你可以隨便找一本介紹數據結構的書看看。當然，如果你用的是c語言，直接利用它的庫類型map、multimap就可以了,它是用紅黑樹實現的，理論上插入、查找時間都是O(logn)，很方便，不過一般會比自己實現的二叉平衡樹稍微慢一些。

⑶ 《演算法導論》三種解遞歸式的方法

代入法可以用來確定一個遞歸式的上界或下界。這種方法很有效，但只能用於解的形式很容易猜的情形。

例如，我們需要確定下面遞歸式的上界：

該遞歸式與歸並排序相似，我們可以猜測其解為

代入法要求證明，恰當選擇常數 c>0，可有 T(n)≤cn lgn。首先假設此上界對所有正數 m<n 都成立，特別是對於 m=n/2，有 T(n/2)≤c(n/2)lg(n/2)。將其代入遞歸式，得到：

其中，只要 c≥1，最後一步都會成立。

並不存在通用的方法來猜測遞歸式的正確解，但總有一些試探法可以幫助做出好的猜測：

如果某個遞歸式與先前見過的類似，則可猜測該遞歸式有類似的解。如，遞歸式

看起來比較難解，因為右式 T 的自變數中加了 17，但我們可以猜測這個多出來的項對解的影響不大，因為當 n 很大時， 與 之間的差別並不大，兩者都將 n 分成均勻的兩半。

另一種方法是先證明遞歸式的較松的上下界，然後再縮小不確定性區間。例如，對遞歸式 ，因為遞歸式中有 n，而我們可以證明初始上界為 。然後，逐步降低其上界，提高其下界，直到達到正確的漸近確界 。

有時，我們或許能夠猜出遞歸式解的漸近界，但卻會在歸納證明時出現一些問題。通常，問題出在歸納假設不夠強，無法證明其准確的界，遇到這種情況時，可以去掉一個低階項來修改所猜測的界，以使證明順利進行。如下面的遞歸式：

可以猜測其解為 ，即要證明對適當選擇的 c，有 。有所猜測的界對遞歸式做替換，得到

由此無法得到 ，無論 c 的值如何。如果猜測一個更大的界，如 ，雖然這確實是上界，但事實上，所猜測的解 卻是正確的。為了證明這一點，要做一個更強的歸納假設。

從直覺上說，猜測 幾乎是正確的，只是差了一個常數 1，即一個低階項，然而，就因為差了一項，數學歸納法就無法證明出期望的結果。從所作的猜測中減去一個低階項，即 是個常數。現在有

只要 b≥ 1。這里，c 要選的足夠大，以便能處理邊界條件。

你可能會覺得從所作的猜測中減去一項有點兒與直覺不符。為什麼不是增加一項來解決問題呢？關鍵在於要理解我們是在用數學歸納法：通過對更小的值作更強的假設，就可以證明對某個給定值的更強的結論。

在運用漸近表示時很容易出錯。例如，對遞歸式 ，由假設 ，並證明

就是錯誤的，因為 c 是常數，因而錯誤地證明了 。錯誤在於沒有證明歸納假設的准確形式，即 。

有時，對一個陌生的遞歸式作一些簡單的代數變換，就會使之變成讀者較熟悉的形式。如下例子：

這個式子看上去比較難，但可以對它進行簡化，方法是改動變數。為了方便起見，不考慮數的截取整數問題，如將 化為整數。設 ，得

再設 ，得到新的遞歸式

這個式子看起來與 就非常像了，這個新的遞歸式的界是： 。將 帶回 ，有 。

有時候，畫出一個遞歸樹是一種得到好猜測的直接方法。在遞歸樹中，每一個節點都代表遞歸函數調用集合中一個子問題的代價。將樹中每一層內的代價相加得到一個每層代價的集合，再將每層的代價相加，得到的結果是所有層次的總代價。當用遞歸式表示分治演算法的運行時間時，遞歸樹的方法尤其有用。

遞歸樹最適合用來產生好的猜測，然後用代入法加以驗證。但使用遞歸樹產生好的猜測時，通常可以容忍小量的「不良量」，因為稍後就會證明所做的猜測。如果畫遞歸樹時非常地仔細，並且將代價都加了起來，那麼就可以直接用遞歸樹作為遞歸式的解的證明。

在講述例子之前，我們先來看一個幾何級數公式

對於實數 x≠1，式

是一個幾何級數（或稱指數級數），其值為

當和是無限的且 |x|<1 時，有無限遞減幾何級數

我們以遞歸式

為例來看一下如何用遞歸樹生成一個好的猜測。首先關注如何尋找解的一個上界，因為我們知道舍入對求解遞歸式通常沒有影響（此處即是我們需要忍受不精確的一個例子），因此可以為遞歸式

創建一顆遞歸樹，其中已將漸近符號改寫為隱含的常數系數 c>0。

構造的遞歸樹如下：

求所有層次的代價之和，確定整棵樹的代價：

最後的這個公式看起來不夠整潔，但我們可以再次充分利用一定程度的不精確，並利用無限遞減幾何級數作為上界。回退一步，得到：

此時，我們得到了遞歸式的一個猜測，在上面的例子里， 系數形成了一個遞減的等比級數，可知這些系數的總和的上界是常數 。由於樹根所需的代價為 ，所以根部的代價占總代價的一個常數部分。換句話說，整棵樹的總代價是由根部的代價所決定的。

事實上，如果 確實是此遞歸式的上界，那麼它一定是確界，為什麼呢？第一個遞歸調用所需要的代價是 ，所以 一定是此遞歸式的下界。

現在我們可以使用代換法來驗證猜測的正確性， 是遞歸式 的一個上界。只需要證明，當某常數 d>0， 成立。適用與前面相同的常數 c>0，有

只要 d≥ ，最後一步都會成立。

上圖是遞歸式

對應的遞歸樹。我們還是使用 c 來代表 項常數因子。當將遞歸樹內各層的數值加起來時，可以得到每一層的 cn 值。從根部到葉子的最長路徑是 。因為當 時， ，所以樹的深度是 。

直覺上，我們預期遞歸式的解至多是層數乘以每層的代價，也就是 。總代價被均勻地分布到遞歸樹內的每一層上。這里還有一個復雜點：我們還沒有考慮葉子的代價。如果這棵樹是高度為 的完整二叉樹，那麼有 個葉子節點。由於葉子代價是常數，因此所有葉子代價的總和為 ，或者說 。然而，這棵遞歸樹並不是完整的二叉樹，少於 個葉子，而且從樹根往下的過程中，越來越多的內部結點在消失。因此，並不是所有層次都剛好需要 cn 代價；越靠近底層，需要的代價越少。我們可以計算出准確的總代價，但記住我們只是想要找出一個猜測來使用到代入法中。讓我們容忍這些誤差，而來證明上界為 的猜測是正確的。

事實上，可以用代入法來證明 是遞歸式解的上界。下面證明 ，當 d 是一個合適的正值常數，則

上式成立的條件是 。因此，沒有必要去更准確地計算遞歸樹中的代價。

主方法給出了求解遞歸式的「食譜」方法，即將規模為 n 的問題劃分為 a 個子問題的演算法的運行時間，每個子問題規模為 ，a 和 b 是正常數。a 個子問題被分別遞歸地解決，時間各為 。劃分原問題和合並答案的代價由函數 描述。

從技術正確性角度來看，遞歸式實際上沒有得到很好的定義，因為 可能不是一個整數。但用 向上取整或向下取整來代替 a 項 並不影響遞歸式的漸近行為，因而，在寫分治演算法時略去向下取整和向上取整函數會帶給很大的方便。

其中我們將 n/b 解釋為 n 除以 b 的向下取整或向上取整。那麼 T(n) 有如下漸近界：

在使用主定理之前，我們需要花一點時間嘗試理解它的含義。對於三種情況的每一種，將函數 f(n) 與函數 進行比較。直覺上，兩個函數較大者決定了遞歸式的解。若函數 更大，如情況 1，則解為 T(n)= ( )。若函數 f(n) 更大，如情況 3，則解為 T(n)= (f(n))。若兩個函數大小相當，如情況 2，則乘上一個對數因子，解為 T(n)= ( )= ( )。

另外還有一些技術問題需要加以理解。在第一種情況下，不僅要有 小於 ，還必須是多項式地小於，也就是說， 必須漸近小於 ，要相差一個因子 ，其中 是大於 0 的常數。在第三種情況下，不是 大於 就夠了，而是要多項式意義上的大於，而且還要滿足「正則」條件 。

注意：三種情況並沒有覆蓋所有可能的 f(n)。當 f(n) 只是小於 但不是多項式地小於時，在第一種情況和第二種情況之間就存在一條「溝」。類似情況下，當 f(n) 大於 ，但不是多項式地大於時，第二種情況和第三種情況之間就會存在一條「溝」。如果 f(n) 落在任一條「溝」中，或是第三種情況種規則性條件不成立，則主方法就不能用於解遞歸式。

使用主方法很簡單，首先確定主定理的哪種情況成立，即可得到解。

例如：

對於這個遞歸式，我們有 a=9，b=3，f(n)=n，因此 = = 。由於 f(n) = ，其中 ， 因此可以應用於主定理的情況 1，從而得到解 T(n) = Θ( ) 。

現在考慮

其中，a = 1， b = 3/2， f(n) = 1，因此 = = = 1 。由於 f(n) = = Θ(1) ，因此可應用於情況2，從而得到解 T(n) = Θ( ) 。

對於遞歸式

我們有 a = 3，b = 4，f(n) = nlgn，因此 = =O( )。由於 當 n，其中 ，因此，如果可以證明正則條件成立，即應用於情況 3。當 n 足夠大時，對於 ， ，因此，由情況 3，遞歸式的解為 T(n)= ( )。

主方法不能用於如下遞歸式：

雖然這個遞歸式看起來有恰當的形式：a=2，b=2， ，以及 。你可能錯誤地認為應該應用情況 3，因為 漸近大於 。問題出現在它並不是多項式意義上的大於。對任意正常數 ，比值 都漸近小於 。因此，遞歸式落入了情況 2 和情況 3 之間的間隙。

證明分為兩部分。第一部分分析「主」遞歸式 ，並作了簡化假設 僅定義在 b>1 的整數冪上，即 ， ， ，…。這部分從直覺上說明該定理為什麼是正確的。第二部分說明如何將分析擴展至對所有的正整數 n 都成立，主要是應用數學技巧來解決向下取整函數和向上取整函數的處理問題。

取正合冪時的證明

對於遞歸式

此時的假設是 n 為 b>1 的正合冪，且 b 不必是整數。分析可分成三個引理說明，第一個引理是將解原遞歸式的問題歸約為對一個含和式的求值的問題。第二個引理決定含和式的界，第三個引理把前兩個合在一起，證明當 n 為 b 的正合冪時主定理成立。

引理一 ：設 a≥1，b>1 為常數，f(n) 為定義在 b 的正合冪上的非負函數。定義 如下：

其中 i 是正整數，則有

證明：如下圖。根節點代價為 f(n)，它有 a 個子女，每個代價是 。（為方便起見可將 a 視為整數，但這對數學推導沒什麼影響。）每個子女又各有 a 個子女，代價為 。這樣就有 個結點離根的距離為 2。一般地，距根為 j 的結點有 個，每一個的代價為 。每一個葉結點的代價為 ，每一個都距根 ，因為 。樹中共有 個葉結點。

可以將樹中各層上的代價加起來而得到方程 ，第 j 層上內部結點的代價為 ，故各層內部結點的總代價和為

在其所基於的分治演算法中，這個和值表示了將問題分解成為子問題並將子問題的解合並時所花的代價，所有葉子的代價（即解 個規模為 1 的子問題的代價）為 。

根據遞歸樹，主定理的三種情況對應於樹中總代價的三種情況：1、由所有葉子節點的代價決定；2、均勻分布在各層上；3、由根結點的代價決定。

引理二 ：設 a≥1，b≥1 為常數， 為定義在 b 的整數冪上的非負函數。函數 由下式定義

對 b 的整數冪，該函數可被漸近限界為：

證明：對情況 1，有 ，這隱含著 。用它對方程 做代換，得

對 O 標記內的式子限界，方法是提出不變項並作簡化，得到一個上升幾何級數：

因為 b 與 都是常數，最後的表達式可化簡為 。用此表達式對 作替換，得

情況 1 得以驗證。

為證情況 2，假設 ，有 。用此式對方程 作替換，得

對 記號中的式子做類似情況 1 中的限界，但所得並非是幾何級數，而是每項都是相同的:

用此方程對 中的和式做替換，有

則情況 2 得以驗證。情況 3 也可以用類似的方式證明。

引理三 ：設 a≥1，b>1 是常量， 是定義在 b 的整數冪上的非負函數。定義 T(n) 如下：

其中 i 是正整數。對於 b 的整數冪，T(n) 可有如下漸近界：

證明：用引理二給出的界來對引理一中的式 求值。對情況 1 有

對情況 2 有

對情況 3 有

⑷ 常見的數據檢索演算法有哪些資料庫都採用什麼樣的檢索方式如何提高檢索的效率

信息檢索方法包括：普通法、追溯法和分段法。1、普通法是利用書目、文摘、索引等檢索工具進行文獻資料查找的方法。運用這種方法的關鍵在於熟悉各種檢索工具的性質、特點和查找過程，從不同角度查找。普通法又可分為順檢法和倒檢法。2、追溯法是利用已有文獻所附的參考文獻不斷追蹤查找的方法，在沒有檢索工具或檢索工具不全時，此法可獲得針對性很強的資料，查准率較高，查全率較差。3、分段法是追溯法和普通法的綜合，它將兩種方法分期、分段交替使用，直至查到所需資料為止。(4)查找方法演算法導論擴展閱讀檢索原因信息檢索是獲取知識的捷徑美國普林斯頓大學物理系一個年輕大學生名叫約瀚·菲利普，在圖書館里借閱有關公開資料，僅用四個月時間，就畫出一張製造原子彈的設計圖。他設計的原子彈，體積小(棒球大小)、重量輕(7.5公斤)、威力大(相當廣島原子彈3/4的威力)，造價低(當時僅需兩千美元)，致使一些國家（法國、巴基斯坦等）紛紛致函美國大使館，爭相購買他的設計拷貝。二十世紀七十年代，美國核專家泰勒收到一份題為《製造核彈的方法》的報告，他被報告精湛的技術設計所吸引，驚嘆地說：「至今我看到的報告中，它是最詳細、最全面的一份。」