中科大软件学院算法复习概念综合题

（1）排序算法时间复杂度：

排序算法插入归并快排

最好O(n)O(nlogn)O(nlogn)

最坏O(n2)O(nlogn)O(n2)

平均O(n2)O(nlogn)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-1

4）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、可合并堆时间复杂度

过程MAKE-HEAPINSERTMINIMUMEXTRACT-MINUNIONDECREASE-KEYDELETE

一颗树的根的最左孩子

性质：

1）共有2k个结点2）树的高度为k

3）在深度i处恰有(上k,下i)（因此叫二项树）个结点，其中i=0,...,k；4）根的度数为k，它大于任何其他结点的度数，并且，如果对根的子女从左到右编号为k-1，k-2,...，0，子女i是子树Bi的根。5）在一颗包含n个结点的二项树中，任意结点的最大度数为lgn3、二项堆H由一组二项树构成，但需要满足下面两个性质：

1）H中的每个二项树遵循最小堆的性质：结点的关键字大于等于其父结点

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~长大了就是要为小时候吹的牛逼而奋斗！加油！---------------MadebyMr.Prisoner二叉堆（最坏）

Θ(1)Θ(lgn)Θ(1)Θ(lgn)Θ(n)Θ(lgn)Θ(lgn)

二项堆（最坏）

Θ(1)Ω(lgn)Ω(lgn)Θ(lgn)Θ(lgn)Θ(lgn)Θ(lgn)

Fibonacci（平摊）

Θ(1)Θ(1)Θ(1)O(lgn)Θ(1)Θ(1)O(lgn)

2、二项树Bk是一种递归定义的树，由两颗Bk-1连接而成，其中一颗树的根是另

算法导论考点总结的关键字。（最小堆性质、度的唯一性）

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和b>1是常数，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)+ε))，且对常数c<1与足够大的n，有a*f(n/b)≤c*f(n)，则T(n)=Ө(f(n))。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~长大了就是要为小时候吹的牛逼而奋斗！加油！---------------MadebyMr.Prisoner算法导论考点总结（7）将41，38，31，12，19，8插入到初试为空的红黑树

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~长大了就是要为小时候吹的牛逼而奋斗！加油！---------------MadebyMr.Prisoner