搜索
算法导论考点总结~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~长大了就是要为小时候吹的牛逼而奋斗！加油！---------------MadebyMr.Prisoner一、概念题：（1）排序算法时间复杂度：排序算法最好最坏平均插入O(n)O(n2)O(n2)归并O(nlogn)O(nlogn)O(nlogn)快排O(nlogn)O(n2)O(nlogn)排序算法空间复杂度：1、所有简单排序和堆排序都是0(1)2、快速排序为0(logn)，要为递归程序执行过程栈所需的辅助空间3、归并排序和基数排序所需辅助空间最多，为O(n)（2）渐近记号1、渐近确界：Θ(g(n))={f(n):存在正常数c1和c2和n0，使对所有的n=n0，都有0=c1g(n)=f(n)=c2g(n)}。大Θ记号给出函数的渐进确界。2、渐近下界：Ω(g(n))={f(n):存在正常数c和n0，使对所有的n=n0，都有0=cg(n)=f(n)}。大Ω记号给出函数的渐进下界。3、渐近上界：O(g(n))={f(n):存在正常数c和n0，使对所有的n=n0，都有0=f(n)=cg(n)}。大O记号给出函数的渐进上界。（3）二叉查找树：执行基本操作的时间与树的高度成正比。搜索、插入、删除的复杂度等于树高，期望O(lgn)，最坏O(n)（数列有序，树退化成线性表）（4）红黑树：1、时间复杂度：基本动态集合操作：O(logn)，n是树中元素的数目。2、性质：1)节点是红色或黑色。2)根节点是黑色。3)每个叶节点（NIL节点）是黑色的。4)如果一个结点是红的，则它的两个儿子都是黑的（不能有两个连续红结点）5)从任一节点到其子孙结点的所有路径都包含相同数目的黑色节点。3、相关概念，定理：1）黑高度：从某个结点出发（不包括该结点）到达一个叶结点的任意一条路径上，黑色结点的个数称为该结点x的黑高度，bh(x)。红黑树的黑高度定义为其根节点的黑高度。2）一颗有n个内结点的红黑树的高度至多为2lg(n+1)。(用2-3-4树理解)3）在一颗黑高度为K的红黑树中，总结点数最多有22k+1-1，此时内结点算法导论考点总结~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~长大了就是要为小时候吹的牛逼而奋斗！加油！---------------MadebyMr.Prisoner最多为22k-1（满二叉树，红黑交替），内结点最少有2k-14）RB-INSERT-FIXUP操作所作的旋转不超过两次，RB-DELETE-FIXUP所作的操作至多三次旋转（5）动态规划：1、装配线调度：FASTEST-WAY时间复杂度O（n）2、矩阵链乘法：MATRIX-CHAIN-ORDER时间复杂度O（n3）3、最长公共子序列：LCS-LENGTH时间复杂度为O（mn），m、n为序列的长度4、最优二叉查找树：OPTIMAL-BST时间复杂度为O（n3）（6）贪心算法：1、活动选择问题：初试时活动已按结束时间排序，O（n），否则可在O（nlgn）内排序2、哈夫曼编码：Q用最小二叉堆实现，运行时间在O（nlgn）3、任务调度问题：时间复杂度为O（n2），因为算法中O（n）次独立性检查中每一次都有花O（n）的时间（7）二项堆：1、可合并堆时间复杂度过程二叉堆（最坏）二项堆（最坏）Fibonacci（平摊）MAKE-HEAPΘ(1)Θ(1)Θ(1)INSERTΘ(lgn)Ω(lgn)Θ(1)MINIMUMΘ(1)Ω(lgn)Θ(1)EXTRACT-MINΘ(lgn)Θ(lgn)O(lgn)UNIONΘ(n)Θ(lgn)Θ(1)DECREASE-KEYΘ(lgn)Θ(lgn)Θ(1)DELETEΘ(lgn)Θ(lgn)O(lgn)2、二项树Bk是一种递归定义的树，由两颗Bk-1连接而成，其中一颗树的根是另一颗树的根的最左孩子性质：1）共有2k个结点2）树的高度为k3）在深度i处恰有(上k,下i)（因此叫二项树）个结点，其中i=0,...,k；4）根的度数为k，它大于任何其他结点的度数，并且，如果对根的子女从左到右编号为k-1，k-2,...，0，子女i是子树Bi的根。5）在一颗包含n个结点的二项树中，任意结点的最大度数为lgn3、二项堆H由一组二项树构成，但需要满足下面两个性质：1）H中的每个二项树遵循最小堆的性质：结点的关键字大于等于其父结点算法导论考点总结~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~长大了就是要为小时候吹的牛逼而奋斗！加油！---------------MadebyMr.Prisoner的关键字。（最小堆性质、度的唯一性）2）对于任意非负整数k，在H中至多有一棵二项树的根具有度数k。二、综合：（1）分治法（自顶向下）1、分解：将原问题分解成一系列子问题2、解决：递归的解各子问题，若子问题足够小，则直接求解3、合并：将子问题的结果合并成原问题的解适用条件：1、原问题可以分解为若干与原问题相似的子问题2、子问题的解可以求出3、子问题的解可以合并成原问题的解4、分解出的子问题应相互独立，即没有重叠子问题（3）合并排序（mergesort）：1、分解：将n个元素分成各含n/2个元素的子序列；2、解决：用合并排序法对两个子序列递归地排序；3、合并：合并两个已排序的子序列以得到排序结果。（4）动态规划（自底向上）：1、描述问题的最优解结构特征2、递归定义最优解值3、自底向上计算最优解值4、从已计算最优解值的信息中构造最优解结构两个要素：最优子结构和重叠子问题（5）贪心算法1、确定问题的最优子结构性质2、将优化的问题转化为一种选择，即贪心选择3、贪心选择只能有一个子问题非空4、证明贪心选择是正确的两个要素：贪心选择性质和最优子结构（6）主方法T(n)=a*T(n/b)+f(n)其中a≥1和b1是常数，f(n)是一个渐近正的函数。n为非负整数，n/b指floor(n/b)或ceiling(n/b)。那么T(n)可能有如下的渐近界：1、若对于某常数ε0，有f(n)=O(n^(log_b(a)-ε))，则T(n)=Ө(n^(log_b(a)))；2、若f(n)=Ө(n^(log_b(a)))，则T(n)=Ө(n^(log_b(a))*lgn)；3、若对某常数ε0，有f(n)=Ω(n^(log_b(a)+ε))，且对常数c1与足够大的n，有a*f(n/b)≤c*f(n)，则T(n)=Ө(f(n))。算法导论考点总结~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~长大了就是要为小时候吹的牛逼而奋斗！加油！---------------MadebyMr.Prisoner（7）将41，38，31，12，19，8插入到初试为空的红黑树