算法答案
- 格式：docx
- 大小：767.51 KB
- 文档页数：10
一、算法的时间复杂度分析。
1. 非递归算法的时间复杂度分析方法；
1.）确定输入规模度量参数。
2.）确定算法基本操作.(通常,基本操作位于最内层循环)。
3.）判断基本操作的执行次数是否仅依赖于输入规模.若有其他因素，则要考虑最坏、平均、最好时间复杂度。
4.）对基本操作次数求和
5.） 利用求和公式得到时间复杂度公式或渐进时间复杂度公式
2.递归算法的时间复杂度分析方法
1.）确定输入规模度量参数Input size.
2.）确定算法基本操作-- basic operation. (通常,基本操作位于最内层循环)
3.） 判断基本操作的执行次数是否仅依赖于输入规模.若有其他因素，则要考虑最坏、平均、最好时间复杂度。
4.）构建递归等式和初始条件
5.）解递归或者确定其生长顺序，计算时间复杂度
3.能够对给定程序代码段，进行相应的时间复杂度分析。
例题：试分析以下算法的时间复杂度
(1) Mergesort (int E[ ], int first, int last)
{ int i, m;
for(m=1;m<=last-first; m+=m)
for(i=first; i<=last-m; i+=2*m)
merge(E, i, i+m-1, min(i+m+m-1,r));
}
这是一个归并算法的非递归实现，开始间隔为1，进行归并，然后以2
为间隔进行归并，以此类推，所以外层for 循环执行次数为
，内层for 循环是有序数组的合并，每次循环需要合并的次数为n/m(m 为两数组的长度和)，而每两个有序数组的时间复杂度为O(a+b),a 和b 分别为两个数组的各自长度，所以内循环的时间复杂度为(n/m)*m=n,所以整个程序的时间复杂度为O(nlogn).
(2) for (i=2;i<=n;i++) log 2n
{
cur=A[i];
for (j =i-1; j>=1; j--)
if ( A[j] > t )
{
t =A[j]; A[j]=A[j+1]; A[j+1]=t; }
else {A[j+1]=cur; break;
}
}
时间复杂度分析：对于程序中的外层循环{i≦n,i++},循环次数为n-1
对于程序中的内层循环{j=i-1,j≥1}
对于外循环所对应的内循环次数为i-1
所以时间复杂度为1+2+3+4.....+n-1=n(n-1)/2从而O(n)=n的平方
二、一些基本数据结构和算法及其效率分析。
红黑树
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。
红黑树的时间复杂度为: O(logn)
红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。
[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
构造红黑树
每次增加的都是红节点，不增加黑高度
如果在红节点上增加红结点，需要进行调整
黑－红－红:换色，转向，调儿子红－黑－红－红:换色，抬高
三、分治策略(Divide and Conquer)
分治法的基本思想是：
将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。
递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。
1.用分治策略对n个元素进行快速排序的平均时间复杂度和最坏时
间复杂度进行分析。
最坏情况：换分的两个区域分别包含n-1的元素和1个元素，也就是
已经排好序的数组，如果用A[0]作为中轴，从左到右的扫描会停止在A[1]上，而从右到左的扫描会一直处理到A[0]导致分裂点出现在0这个位置，所以，在进行了n+1次比较之后建立了分区，并且将A[0]和它本身进行了交换以后，快速排序算法还会对严格递增的数组A[1,2,3,....n-1]进行排序，对规模减小了的严格递增数组的排序会一直继续到左后一个子数组A[n-2,n-1]，这种情况下，键值比较的总次数应该等于:(n+1)+n+......+3=O()
平均情况：假设待排序的元素服从独立均匀随机分布，于是，快速排序算法在经过n-1次比较和之多n+1次移动操作后，对规模为n 的向量的划分结果无非n 种可能，划分所得左侧子序列的长度分别是0,1,2,3......,n-1，分别取决于所取候选元素在最终有序序列中的秩，按假定条件，每种情况的概率均为1/n ，设该算法的平均时间为T(n)，
T(n)=(n+1)+(1/n)*==(n+1)+(2/n)* 解得O(n)=0(nlogn)
2. 用分治策略对n 个元素进行归并排序的平均时间复杂度和最坏时间复杂度进行分析
归并排序归并排序是采用分治法（Divide and Conquer ）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。
元素长度为n 的归并排序所消耗的时间为：调用数组划分函数划分为两部分，那每一小部分排序好所花时间则n 2∑=-+-n k n T k T 1k )]()1([∑=-n k k T 1)1(
为;T[n/2]，而最后把这两部分有序的数组合并成一个有序的数组所花的时间为;O(n)；因为不管元素在什么情况下都要做这些步骤，所以花销的时间是不变的，所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为：O( nlogn )
3.列举几种对快速排序和归并排序的改进点。
插入归并
归并排序的时间复杂度为O(nlgn)，一般来讲，基于从单个记录开始两两归并的排序并不是特别提倡，一种比较常用的改进就是结合插入排序，即先利用插入排序获得较长的有序子序列，然后再两两归并（改进后的归并亦是稳定的，因为插入排序是稳定的）。
原因的：尽管插入排序的最坏情况是O(n^2)，看起来大于归并的最坏情况O(nlgn)，但通常情况下，由于插入排序的常数因子使得它在n比较小的情况下能运行的更快一些，因此，归并时，当子问题足够小时，采用插入排序是比较合适的。
4.简述利用分治策略进行问题分析解决的主要过程
分治策略求解一个问题，主要有三个步骤，分解：将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
解决：递归的求解出子问题，如果子问题的规模足够小，则递归停止，直接求解。
合并：将子问题的解组合成原问题的解。
四、均摊策略(Amortizing Analyses)
用均摊策略讨论采用Array doubling方法对n个元素进行动态存储
时的时间复杂度
采用Array doubling 对n 个元素动态存储，在进行存储时分为两种情况
（1）：当空间足够时，直接插入一个元素即可，时间消耗为T(1)
（2）:当存储空间不够时，将空间扩展为原来的两倍，将原空间的的元素全部复制到新的空间，并且插入最新要插入的一个元素，此时的时间消耗分为两部分（复制元素和插入元素），所以T(n)=n+,(n 为插入n 个元素的时间消耗，为复制元素的总时间消耗)
T(n)=n+=n+-1=n+2(n-1)≤3n
所以时间复杂度为O(n)
s k s k ∑-=1
2
log 02n j j q 1)1(2
log ++n。
