算法分析与设计复习提纲.docVIP

第=1+1页共sectionpages11页

第一章算法基础

算法（algorithm）是什么？

一个算法是对特定问题求解步骤的一种描述，它是指令的有限序列。

算法的五个特征：

输入(input)：算法有零个或多个输入量；

输出(output)：算法至少产生一个输出量；

确定性(definiteness)：算法的每一条指令都有确切的定义，没有二义性；

能行性(effectiveness)：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现；

有穷性(finiteness)：算法必须总能在执行有限步之后终止。

程序(Program)是算法用某种程序设计语言的具体实现。算法必须可终止，程序却没有这一限制。Windows是程序不是算法。

一个好的算法应具有以下4个重要特性:

正确性(correctness)：算法的执行结果应当满足预先规定的功能和性能要求。

简明性(simplicity)：算法应思路清晰、层次分明、容易理解、利于编码和调试。

效率(efficiency)：算法应有效使用存储空间，并具有高的时间效率。

最优性（optimality）：算法的执行时间已达到求解该类问题所需时间的下界。

第二章算法分析

渐近分析中函数比较

f(n)=O(g(n))≈f(n)≤g(n);（渐进上界）

f(n)=Ω(g(n))≈f(n)≥g(n);（渐进下界）

f(n)=Θ(g(n))≈f(n)=g(n);（紧渐紧界）

f(n)=o(g(n))≈f(n)g(n);（非紧渐进上界）

f(n)=ω(g(n))≈f(n)g(n).（非紧渐进下界）

传递性：都有

反身性f(n)=Θ(f(n))；f(n)=O(f(n))；f(n)=Ω(f(n)).，

对称性：f(n)=Θ(g(n))?g(n)=Θ(f(n)).

互对称性：f(n)=O(g(n))?g(n)=Ω(f(n))；f(n)=o(g(n))?g(n)=ω(f(n))；

算术运算：

O(f(n))+O(g(n))=O(max{f(n),g(n)})；

O(f(n))+O(g(n))=O(f(n)+g(n))；

O(f(n))*O(g(n))=O(f(n)*g(n))；

O(cf(n))=O(f(n))；其中c是一个正的常数；

如果g(n)=O(f(n))?则O(f(n))+O(g(n))=O(f(n))。

f=O(f)。

最常见的多项式时间算法的渐近时间复杂度

O(1)＜O(logn)＜O(n)＜O(nlogn)＜O(n^2)＜O(n^3)

最常见的指数时间算法的渐近时间复杂度

O(2n)＜O(n!)＜O(n^n)

求T（n）表达式：

T(n)=2T(n?1)+1

=2(2T(n?2)+1)+1

=2^2T(n?2)+2+1

=2^3T(n?3)+2^2+2+1

…

=2^(n?1)T(1)+…+2^2+2+1

=2^(n?1)+…+2^2+2+1

=2^n?1

第五章分治法

分治法的基本思想：

将一个复杂的问题分解成若干个规模较小、相互独立，但类型相同的子问题求解；然后再将各子问题的解组合成原始问题的一个完整答案。

一个问题能够用分治法求解的要素是：

1，问题能够按照某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题；2，子问题足够小时可以直接求解；3，能够将子问题的解组合成原问题的解。

两路合并排序：

templateclassT

voidSortableListT::Merge(intleft,intmid,intright)

{T*temp=newT[right-left+1];

inti=left,j=mid+1,k=0;

while((i=mid)(j=right))

if(l[i]=l[j])temp[k++]=l[i++];

elsetemp[k++]=l[j++];

while(i=mid)temp[k++]=l[i++];

while(j=right)temp[k++]=l[j++];

for(i=0,k=left;k=right;)l[k++]=temp[i++];

}

templateclassT

voidSortableListT::MergeSort(intleft,intright)

{if(leftright)

{intmid=(left+right)/2;

MergeS