查找方法算法导论

⑴ 算法导论的作品目录

目录（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的威力)，造价低(当时仅需两千美元)，致使一些国家（法国、巴基斯坦等）纷纷致函美国大使馆，争相购买他的设计拷贝。二十世纪七十年代，美国核专家泰勒收到一份题为《制造核弹的方法》的报告，他被报告精湛的技术设计所吸引，惊叹地说：“至今我看到的报告中，它是最详细、最全面的一份。”