第一章 算法引论

算法设计与分析王喜凤wxf80106@126.com课程学时总学时：24学时；其中讲课：18学时；上机：6学时参考资料[1]王晓东.算法设计与分析（第二版）.清华大学出版社，2008.1[2]算法设计与分析习题解答王晓东编著清华大学出版社2006[3]SaraBaase等.计算机算法-设计与分析导论（英文第三版影印版）.高等教育出版社，2001.7Web资源,,…课程目标—性质、类型、地位专业基础课选修课计算机科学的核心性质类型地位课程目标—教学目标算法分析能力算法设计能力训练计算思维可用计算机有效解决常见实际问题具体用处可从计算机角度，建立常见问题的解决思路比赛：如ACM（ICPC）、TopCoder

考硕士(复试科目)或博士（考试科目）课程主要内容第1章 算法引论第2章 递归与分治策略第3章 动态规划第4章 贪心算法第5章 回溯法第6章 分支限界法第7章 概率算法第8章 NP完全性理论第9章 近似算法第10章算法优化策略第1章算法引论1.1 算法与程序1.2算法与数据结构1.3表达算法的抽象机制1.4描述算法与算法设计1.5算法分析的基本原则1.6算法复杂性分析本章主要知识点：1.0算法概述很难给算法（algorithm）给出精确的定义。“算法是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。”计算机科学中，算法已逐渐成了用计算机解一类问题的精确、有效方法的代名词。

课程目标—地位1.1 算法与程序算法：是满足下述性质（特性）的指令序列。输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。程序：程序是算法的某种程序设计语言的描述。程序可以不满足算法的性质(4)即有限性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。1.2 算法与数据结构算法操作的对象是数据，数据间的逻辑关系、数据的存储方式及处理方式就是数据的数据结构。它与算法设计是紧密相关的。算法与数据结构的关系不了解施加于数据上的算法就无法决定如何构造数据，可以说算法是数据结构的灵魂；反之算法的结构和选择又常常在很大程度上依赖于数据结构，数据结构则是算法的基础。算法＋数据结构＝程序课程目标—地位算法+数据结构=程序武林大会兵器：刀、剑、棒课程目标—地位算法+数据结构=程序武林大会兵器：刀、剑、棒招式课程目标—地位算法+数据结构=程序武林大会兵器：刀、剑、棒招式1.3 表达算法的抽象机制从机器语言到高级语言的抽象高级程序设计语言的主要好处是：高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；把繁琐的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。1.3 表达算法的抽象机制抽象数据类型抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。抽象数据类型带给算法设计的好处有：算法顶层设计与底层实现分离；算法设计与数据结构设计隔开，允许数据结构自由选择；数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；用抽象数据类型表述的算法具有很好的可维护性；算法自然呈现模块化；为自顶向下逐步求精和模块化提供有效途径和工具；算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。1.4 描述算法与算法设计描述算法可以有多种方式，如自然语言方式、图形表格方式等。本书采用Java与自然语言相结合的方式；本人对语言不做任何限制：C++、C#、VB……1.4 描述算法与算法设计问题求解(ProblemSolving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构和算法设计策略设计算法1.5 算法复杂性分析why？设一台作109次/秒运算（1G）的计算机的效率超过10亿人同时工作。IBM研发单芯片超级计算机速度达1万亿次/秒2003-9-1比如拿最简单例子，26个英文字母全排列，它的排列数为：26！≈4×1026以每年365天计算，共有

365×24×3600＝3.1536×107秒以每秒能完成109个排列的超高速电子计算机来做这项工作，需要4×1026/(3.1536×1016)≈1.2×1010年即使计算机运行速度随着技术的提高，恐怕也还是不可能实现的。因计算机的速度再提高也有它的极限。1.5 算法复杂性分析算法复杂性是算法运行所需要的计算机资源量，需要的时间资源量称为时间复杂性，需要的空间资源量称为空间复杂性。这个量应该是只依赖于问题的规模(N)、算法的输入(I)和算法本身的函数(A)。用C表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I)

。（通常，让A隐含在复杂性函数名当中）算法复杂性=算法所需要的计算机资源算法的时间复杂性T(n)；算法的空间复杂性S(n)。其中n是问题的规模（输入大小）。算法复杂度是指算法时间与问题规模的关系1.5 算法复杂性分析最坏情况下的时间复杂性：k种元运算，每种运算的时间为ti，元运算的次数为ei最好情况下的时间复杂性：平均情况下的时间复杂性：其中DN是规模为N的合法输入的集合；I*是DN中使T(N,I*)达到Tmax(N)的合法输入；是中使T(N,)达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。1.5算法复杂性表达形式函数的渐进性态与渐进表达式：一般来说，当N单调增加且趋于∞时，T(N)也将单调增加趋于∞。对于T(N)，如果存在函数T'(N)，使得当N→∞使有(T(N)-T'(N))/T(N)→0，那么我们就说T'(N)是T(N)当N→∞时的渐进性态。在数学上，T'(N)是T(N)当N→∞时的渐进表达式。例如：3N2+4NlogN+7与3N2。1.5算法复杂性表达形式算法复杂性在渐近意义下的阶：渐近意义下的记号：O设f(N)和g(N)是定义在正数集上的正函数。O的定义：如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≤Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。即f(N)的阶不高于g(N)的阶。根据O的定义，容易证明它有如下运算规则：O(f)+O(g)=O(max(f,g))；O(f)+O(g)=O(f+g)；O(f)O(g)=O(fg)；如果g(N)=O(f(N))，则O(f)+O(g)=O(f)；O(Cf(N))=O(f(N))，其中C是一个正的常数；f=O(f)。T（n）=3n+2=O（n）1.5算法复杂性表达形式规则Ｏ(f(n))+Ｏ(g(n))=Ｏ(max{f(n),g(n)})的证明：对于任意f1(n)=Ｏ(f(n))，存在正常数c1和自然数n1，使得对所有n≥n1，有f1(n)≤c1f(n)。类似地，对于任意g1(n)=Ｏ(g(n))，存在正常数c2和自然数n2，使得对所有n≥n2，有g1(n)≤c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，

h(n)=max{f(n),g(n)}。则对所有的n≥n3，有

f1(n)+g1(n)≤c1f(n)+c2g(n)≤c3f(n)+c3g(n)=c3(f(n)+g(n))≤c32max{f(n),g(n)}

＝

2c3h(n)＝Ｏ(max{f(n),g(n)}).1.5算法的时间复杂性例1sum=0；

（一次）

for(i=1;i<=n;i++)

（n次）

for(j=1;j<=n;j++)（n2次）

sum++；

（n2次）

解：T(n)=2n2+n+1=O(n2)1.5算法的时间复杂性例1：a=0;

b=1;

①

for(i=1;i<=n;i++)②

{

s=a+b;

③

b=a;

④

a=s;

⑤

}

解：语句1的频度：1＋1＝2,

语句2的频度：n,

语句3的频度：n-1,

语句4的频度：n-1,

语句5的频度：n-1,

T(n)=2+n+3(n-1)=4n-1=O(n)。1.5算法的时间复杂性例3i=1;

①while(i<=n)

i=i*2;②

解：语句1的频度是1，设语句2的频度是f(n)，

则：

2f(n)<=n;f(n)<=log2n，

取最大值f(n)=log2n,T(n)=O(log2n)。1.5最坏情况下的时间复杂性例4冒泡排序算法的基本步骤如下：voidBubbleSort(SeqListR)

{//R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序

inti，j；Booleanexchange；//交换标志

for(i=1;i<n;i++){//最多做n-1趟排序

exchange=FALSE；//本趟排序开始前，交换标志应为假

for(j=n-1;j>=i；j--)//对当前无序区R[i..n]自下向上扫描

if(R[j+1].key<R[j].key){//交换记录R[j+1]，R[j]交换；

exchange=TRUE；//发生了交换，故将交换标志置为真

}

if(!exchange)//本趟排序未发生交换，提前终止算法

return；

}//endfor(外循环)

}//BubbleSort当输入的数据已经排好序，只要比较n-1次；当输入的数据是降序，要比较n(n-1)/2时间复杂度精确表示？？？T（n）=n2+2渐进？？1.6算法分析的基本原则正确性定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法是正确的。正确性证明的内容：方法的正确性证明——算法思路的正确性。证明一系列与算法的工作对象有关的引理、定理以及公式。//理论上是否正确程序的正确性证明——证明所给出的一系列指令确实做了所要求的工作。//实践上是否正确程序正确性证明的方法：大型程序的正确性证明——可以将它分解为小的相互独立的互不相交的模块，分别验证。小模块程序可以使用以下方法验证：数学归纳法等。1.6算法分析的基本原则工作量——时间复杂性分析计量工作量的标准:对于给定问题，该算法所执行的基本运算的次数。基本运算的选择：根据问题选择适当的基本运算。问题基本运算在表中查找x比较实矩阵相乘实数乘法排序比较遍历二叉树置指针1.6算法分析的基本原则占用空间——空间复杂性分析两种占用：存储程序和输入数据的空间存储中间结果或操作单元所占用空间——额外空间影响空间的主要因素：存储程序的空间一般是常数(和输入规模无关)输入数据的空间O(n)(n为输入规模)空间复杂性考虑的是额外空间的大小1.6算法分析的基本原则简单性含义：算法简单，程序结构简单。好处：容易验证正确性便于程序调试简单的算法效率不一定高。要在保证一定效率的前提下力求得到简单的算法。1.6算法分析的基本原则最优性含义：指求解某类问题中效率最高的算法两种最优性最坏情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在最坏情况下的时间复杂性比A在最坏情况下的时间复杂性低，则称A是解这个问题在最坏情况下的最优算法。平均情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在平均情况下的时间复杂性比A在平均情况下的时间复杂性低，则称A是解这个问题在平均情况下的最优算法。1.6算法分析的基本