搜索
《算法导论》学习笔记Version1.0项目托管：：：chuanqi.tan(at)gmail.com欢迎交流与反馈错误等，转载及引用请注明ByHannosogno@BIT2011QQ121131818第一部分：基础知识第1章：算法在计算中的作用1.算法即是一系列的计算步骤，用来将一个有效的输入转换成一个有效的输出。2.计算机的有限的资源必须被有效的利用，算法就是来解决这些问题的方法。第2章：算法入门1.循环不变式的三个性质：（循环不变式通常用来证明递归的正确性）1.初始化：它在循环的第一轮迭代开始之前，应该是正确的。2.保持：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确。3.终止：当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。2.伪代码中的约定：1.书写上的“缩进”表示程序中的分程序（程序块）结构。2.while,for,repeat等循环结构和if,then,else条件结构与Pascal中相同。3.符号▷”表示后面部分是个注释。4.多重赋值i←j←e是将表达式e的值赋给变量i和j；等价于j←e，再进行赋值i←j。5.变量（如i,j和key等）是局部给定过程的。6.数组元素是通过“数组名[下标]”这样的形式来访问的。7.复合数据一般组织成对象，它们是由属性(attribute)和域(field)所组成的。8.参数采用按值传递方式：被调用的过程会收到参数的一份副本。9.布尔运算符and”和or”都是具有短路能力。3.算法分析即指对一个算法所需要的资源进行预测。4.对于一个算法，一般只考察其最坏情况的运行时间，理由有三：1.一个算法的最坏情况运行时间是在任何输入下运行时间的一个上界。2.对于某些算法来说，最坏情况出现得还是相当频繁的。3.大致上看来，“平均情况”通常和最坏情况一样差。5.分治策略：将原问题划分成ｎ个规模较小而结构与原问题相似的子问题；递归地解决这些小问题，然后再合并其结果，就得到原问题的解。6.分治模式在每一层递归上都有三个步骤：1.分解(Divde)：将原问题分解成一系列子问题；2.解决(Conquer)：递归地解答各子问题。若子问题足够小，则直接求解；3.合并(Combine)：将子问题的结果合并成原问题的解。第3章：函数的增长1.对几个记号的大意：o（非渐近紧确上界）≈；O（渐近上界）≈≤；Θ（渐近紧界）≈=；Ω（渐近下界）≈≥；ω（非渐近紧确下界）≈;这里的,≤,=,≥,指的是规模上的比较，即o(g(n))的规模比g(n)小。o(g(n))={f(n):对任意正常数c，存在常数n00，使对所有的n≧n0，有0≦f(n)cg(n)}O(g(n))={f(n):存在正常数c和n0，使对所有n≧n0，有0≦f(n)≦cg(n)}Θ(g(n))={f(n):存在正常数c1，c2和n0，使对所有的n≧n0，有0≦c1g(n)≦f(n)≦c2g(n)}Ω(g(n))={f(n):存在正常数c和n0，使对所有n≧n0，有0≦cg(n)≦f(n)}ω(g(n))={f(n):对任意正常数c，存在常数n00，使对所有的n≧n0，有0≦cg(n)f(n)}第4章：递归式8.递归式是一组等式或不等式，它所描述的函数是用在更小的输入下该函数的值来定义的。例如Merge-Sort的最坏情况运行时间T(n)可以用以下递归式来表示：{9.解递归式的方法主要有三种：代换法、递归树方法、主方法。10.代换法(Substitutionmethod)(P38~P40)定义：先猜测某个界的存在，再用数学归纳法去证明该猜测的正确性。缺点：只能用于解的形式很容易猜的情形。总结：这种方法需要经验的积累，可以通过转换为先前见过的类似递归式来求解。11.递归树方法(Recursion-treemethod)起因：代换法有时很难得到一个正确的好的猜测值。用途：画出一个递归树是一种得到好猜测的直接方法。分析(重点)：在递归树中，每一个结点都代表递归函数调用集合中一个子问题的代价。将递归树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。总结：递归树最适合用来产生好的猜测，然后用代换法加以验证。递归树的方法非常直观，总的代价就是把所有层次的代价相加起来得到。但是分析这个总代价的规模却不是件很容易的事情，有时需要用到很多数学的知识。12.主方法(Mastermethod)主方法是最好用的Cookbook方法，太神奇了，可以瞬间估计出递归算法的时间复杂度，主方法总结了常见的情况并给出了一个公式。优点：针对形如T(n)=aT(n/b)+f(n)的递归式缺点：并不能解所有形如上式的递归式的解。因为主方法在第1种情况与第2种情况之间、第2种情况与第3种情况之间都存在着一条沟，所以会存在着不能适用的情况。直觉上：实际上主方法一直在比较f(n)与NLogba的规模，然后选取规模大的作为最后的递归式的规模。主方法：设a≥1和b≥1是常数f(n)是定义在非负整数上的一个确定的非负函数。又设T(n)也是定义在非负整数上的一个非负函数，且满足递归方程T(n)=aT(n/b)+f(n)。方程T(n)=aT(n/b)+f(n)中的n/b可以是[n/b]，也可以是n/b。那么，在f(n)的三类情况下，我们有T(n)的渐近估计式：1.若对于某常数ε0，有，则；2.若，则；3.若对其常数ε0，有且对于某常数c1和所有充分大的正整数n有af(n/b)≤cf(n)，则T(n)=θ(f(n))。第5章：概率分析与随机算法1：随机算法：如果一个算法的行为不只是由输入决定，同时也由随机数生成器所产生的数值决定，则称这个算法是随机的。2：指示器随机变量I(A)的定义很简单：{如果不发生的话如果发生的话事件A对应的指示器随机变量的期望期等于事件A发生的概率。3：介绍了两种随机排列数组的生成方法：1.随机优先级法：为数组的每个元素赋一个随机的优先级，再根据这个优先级对数组中的元素进行排序。可证这样得到的数字满足随机的性质。2.原地交换法：依次把A[i]与A[Random(i+1,Length(A))]进行swap，得到的新数组也满足随机性。fori←1tondoswapA[i]↔A[Random(i,Length(A))]4：有时间，在真正的环境中的输入可能并不是随机的，所以我们可以采用先将输入进行随机打乱的方法来保证输入数据的随机性，这点在很多算法中得以体现，比如快排有其随机选取种子数来向输入中加入随机化的成分。5：===5.4节带*未看===不过值得提一下的是“在线雇佣问题”与“苏格拉底的择偶观”很相似。先用三分之一的时间，即分出大、中、小三类，再用三分之一的时间验证自己的观点是否正确，等到最后三分之一时，选择了属于大类中的一支美丽的麦穗。第二部分：排序和顺序统计学1：这一部分将要给出几个解决以下排序问题的算法：输入：n个数的序列a1,a2,…an输出：输入序列的一个重排a1’,a2’,...,an’，使a1’≦a2’≦...≦an’2：原地排序算法：只有线性个数的元素会被移动到集合之外的排序算法。3：第6章介绍堆排序4：第7章介绍快速排序5：第8章介绍了基于“比较”排序的算法的下界为Ω(nlgn)。并介绍了几种不基于比较的排序方法，它们能突破Ω(nlgn)的下界。计数排序、基数排序、桶排序。6：第9章介绍了顺序统计的概念：第i个顺序统计是集合中第i小的数。并介绍了两个算法：最坏情况为O(n^2)，但平均情况下为线性O(n)的算法最坏情况下为线性O(n)的算法第6章：堆排序1：堆排序是一个时间复杂度为O(nlgn)、原地排序算法。2：“堆”数据结构不只在推排序时有用，还可以构成一个有效的优先队列（堆的主要应用之一）。3：堆的定义是这样的：一个堆是一颗完全二叉树对于大（小）根堆每个节点的值都比它的子节点要大（小）4：虽然堆排的理论效率好，但是往往一个好的快排的实现要优于堆排。5：所以堆更常见于作为高效的优先级队列：一个堆可以在O(lgn)的时间内，支持大小为n的集合上的任意优先队列的操作。Output（代码：）:原始数组，准备进行堆排序：85784564987453423423堆排序结束：45823233445456478987初始化一个优先队列：41169334358464724478500962467开始不断的取最高优先级的任务出列：41:169358334467464724478500962169:334358478467464724962500334:358464478467500724962358:464467478962500724464:467500478962724467:478500724962478:500962724500:724962724:962962:开始添加任务入列：445458458234582323458232334458232334454582323344545458232334454564458232334454564784582323344545647898745823233445456478987请按任意键继续...第7章：快速排序1：快速排序的最坏运行时间为O(n2)，期望运行时间为O(nlgn)，且由于O(nlgn)中隐含的常数因子很小，所以快排通常是用于排序的最佳的实用选择（因为其平均性能非常好）。快排真的太棒了：平均性能非常好、原地排序不需要额外的空间、算法简单只需要寥寥几行就搞定（比冒泡还少）。对10W个随机数进行排序比较，快排平均在600MS，而堆排平均在900MS，性能差距可见一斑啊。2：快排的平均情况运行时间与其最佳情况运行时间很接近，而不是非常接近于其最坏情况运行时间，所以一般来说快排效率是最高的，这是快排在现代得以大规模的使用的根本原因。3：快排很需要随机化技术：因为在真正的应用时很容易出现待排序的数组其实已经是有序的情况，而这种已经有序的情况却正好又是快排算法的软肋，它在待排数组有序时的效率是最差的O(n^2)，所以很需要随机化技术！4：快速排序的随机化版本：正如第5章所说的，由于工程中的输入可能不随机的，所以我们要将其随机化。有两种可选方案（1）直接对输入数据进行随机化排列（2）采用随机取样的随机化技术。随机取样的效率更高一些，所以在快速排序的随机化版本中采用随机取样的技术。方法很简单，就是在每趟sort之前随机选取一个数与最未尾的元素进行交换操作，这样简单高效的实现了随机化。//加入随机取样的随机化技术intrandom_swap=(rand()%(EndIndex-BeginIndex+1))+BeginIndex;std::swap(ToSort[random_swap],ToSort[EndIndex]);这个技术太有用啊，因为快速排序在输入数据已经有序时的性能是最差的，但是输入数据已经有序的情况又会经常发生，所以这个随机取样就显得异常的重要。如果没有这个随机取样，快排绝得不到这样的应用。在我做的实验中，对2000个有序的数据进行排序，在未没采用随机化的情况下，平均耗时860MS，而使用了随机取样之后平均耗时8MS，效率提高了100倍。由于输入有序的情况是非常常见的，所以这个随机化才更显示重要了！Output（代码：）:==========================快速排序===================