计算机算法设计与分析-第1章-算法概述

计算机算法设计与分析

DesignandAnalysisofComputerAlgorithms

第一章算法概述10/11/20241理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用C++语言描述算法的方法学习要点:2提纲一、算法与程序二、算法复杂性分析三、用C++语言描述算法的方法3提纲一、算法与程序二、算法复杂性分析三、用C++语言描述算法的方法41.1算法的概念算法是指解决问题的方法和过程。算法是对特定问题求解步骤的一种描述，包含操作的有限规则和操作的有限序列。通俗一点讲，算法就是一个解决问题的公式（数学手册上的公式都是经典算法）、规则、思路、方法和步骤。算法可以用自然语言描述，也可以用流程图描述，但最终要用计算机语言编程，上机实现。

5算法是若干指令的有穷序列，满足性质：输入：有1个或多个满足给定约束条件的量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令是清晰，无歧义的。有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。算法要求其执行时间是有限的(终止性)。程序的执行时间可能是无限的。(例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。

)6程序程序是某个算法或过程的在计算机上的一个具体的实现。程序是依赖于程序设计语言的，甚至依赖于计算机结构的。算法是脱离具体的计算机结构和程序设计语言的。7算法与程序的区别与联系

(1).一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。(2).程序中的指令必须是机器可执行的，而算法中的指令则无此限制。

(3).算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序.8算法≠程序算法描述：自然语言，流程图，程序设计语言，伪代码用各种算法描述方法所描述的同一算法，该算法的功用是一样的，允许在算法的描述和实现方法上有所不同。本书中采用类C++伪代码语言描述算法9人们的生产活动和日常生活离不开算法，都在自觉不自觉地使用算法，例如人们到商店购买物品，会首先确定购买哪些物品，准备好所需的钱，然后确定到哪些商场选购、怎样去商场、行走的路线，若物品的质量好如何处理，对物品不满意又怎样处理，购买物品后做什么等。以上购物的算法是用自然语言描述的，也可以用其他描述方法描述该算法。

10对算法的学习包括五个方面的内容：①设计算法。②表示算法。③确认算法。④分析算法。⑤验证算法。11①设计算法。算法设计工作是不可能完全自动化的，应学习了解已经被实践证明是有用的一些基本的算法设计方法，这些基本的设计方法不仅适用于计算机科学，而且适用于电气工程、运筹学等领域；②表示算法。描述算法的方法有多种形式，例如自然语言和算法语言，各自有适用的环境和特点；12③确认算法。算法确认的目的是使人们确信这一算法能够正确无误地工作，即该算法具有可计算性。正确的算法用计算机算法语言描述，构成计算机程序，计算机程序在计算机上运行，得到算法运算的结果；④分析算法。算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。分析算法可以预测这一算法适合在什么样的环境中有效地运行，对解决同一问题的不同算法的有效性作出比较；⑤验证算法。用计算机语言描述的算法是否可计算、有效合理，须对程序进行测试，测试程序的工作由调试和作时空分布图组成。

131.2问题表示设Input和Output是两个集合。一个问题是一个关系R

Input

Output，Input称为问题R的输入集合，Input的每个元素称为R的一个输入，Output称为问题R的输出或结果集合，Output的每个元素称为R的一个结果。一个算法面向一类问题，而不是仅求解问题的一个或几个实例。141.2问题表示例如，排序（SORT）问题定义如下：－Input=

<a1,....,an>

ai是实数

－output=

<b1,....,bn>

bi是实数,且b1

...

bn

－R=

(<a1,...,an>,<b1,...,bn>)

<a1,...,an>

Input，<b1,...,bn>

output,

a1,...,an

=

b1,...,bn}15a

0,...,n-1

=5,2,4,6,1,3a

0,...,n-1

=5,2,4,6,1,3a

0,...,n-1

=2,5,4,6,1,3a

0,...,n-1

=2,4,5,6,1,3a

0,...,n-1

=2,4,5,6,1,3a

0,...,n-1

=1,2,4,5,6,3a0,...,n-1

=1,2,3,4,5,6算法的思想：扑克牌游戏1.3算法示例—插入排序算法16算法描述

1.从第一个元素开始，该元素可以认为已经被排序

2.取出下一个元素，在已经排序的元素序列中从后向前扫描

3.如果该元素（已排序）大于新元素，将该元素移到下一位置

4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

5.将新元素插入到该位置中

6.重复步骤2171.3算法示例插入排序算法

template<classType>voidInsertionSort(Type*a,intn)//数组a中包含了n个待排序的数.{Typekey;for(inti=1;i<n;i++){key=a[i];//Inserta[i]intothesortedsequencea[0..i-1].

intj=i-1;while(j>=0&&a[j]>key){ a[j+1]=a[j]; j--; }a[j+1]=key;}}181.4算法的正确性分析正确的算法：对于每一个输入都最终停止,而且产生正确的输出。不正确算法：①不停止(在某个输入上)②对所有输入都停止，但对某输入产生不正确结果近似算法①对所有输入都停止②产生近似正确的解或产生不多的不正确解算法正确性证明证明算法对所有输入都停止证明对每个输入都产生正确结果调试程序

程序正确性证明！程序调试只能证明程序有错，不能证明程序无错误!191.4算法的正确性分析算法正确性证明的步骤：初始化算法在循环的第一步迭代开始之前，应该是正确的。保持如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确。终止当循环结束时，算法也应该是正确的。分析前面插入排序算法的正确性20算法设计与分析的基本方法

1.递推法

递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系，从而达到目的，此方法称为递推法。

212.递归

递归指的是一个过程：函数不断引用自身，直到引用的对象已知

3.穷举搜索法

穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。

224.贪婪法

贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。

235.分治法

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

246.动态规划法

动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。

257.迭代法

迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。26提纲一、算法与程序二、算法复杂性分析三、用C++语言描述算法的方法27同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

28二、算法复杂性分析算法复杂性=算法所需要的计算机资源所需资源量越多则复杂性越高，反之所需资源量越少则复杂性越低。其中最为重要的是：时间复杂性T(n)；空间复杂性S(n)。其中n是问题的规模（输入大小）。示例：一维数组问题的输入大小＝数组的长度矩阵问题的输入大小=矩阵的维数图论问题的输入大小=图的边数/结点数29决定算法复杂性的因素算法的复杂性取决于(1)求解问题的规模；(2)具体的输入数据；(3)算法本身的设计。若令N、I、和A分别表示问题的规模、具体的输入和算法本身，则C=F(N,I,A)或C=FA(N,I)=F(N,I)30时间复杂性的计算时间复杂性T(N,I)的计算为：

其中：ti为执行抽象计算机的第i种指令一次所需要的时间，这里假定抽象计算机共有k种指令。ei(N,I)为经过统计后得到的执行抽象计算机的第i种指令的次数。

kT(N,I)=

ti

ei(N,I)

i=131二、算法复杂性分析算法分析的目的：设计算法——设计出复杂性尽可能低的算法选择算法——在多种算法中选择其中复杂性最低者322.1算法时间复杂性最坏情况下的时间复杂性

Tmax(n)=max{T(I)|size(I)=n}最好情况下的时间复杂性

Tmin(n)=min{T(I)|size(I)=n}平均情况下的时间复杂性

Tavg(n)=

其中I是问题的规模为n的实例，p(I)是实例I出现的概率。332.2时间复杂性计算为了能够较客观的反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。基本运算反映了算法运算的主要特征，因此，用基本运算的次数来度量算法工作量是客观的也是实际可行的，有利于比较同一问题的几种算法的优劣。例如，在考虑两个矩阵相乘时，可以将两个实数之间的乘法运算作为基本运算.342.2时间复杂性计算在一般的计算机系统中，基本的运算和操作有以下四类：

①算术运算：主要包括加、减、乘、除等运算。

②逻辑运算：主要包括“与”、“或”、“非”等运算。

③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算。

④数据传输：主要包括赋值、输入、输出等操作。规定其中每条指令所需的时间都为常量。算法的执行时间=原子操作的执行次数×原子操作的执行时间35

template<classType>voidInsertionSort(Type*a,intn){Typekey;//costtimesfor(inti=1;i<n;i++){//c1n

key=a[i];//c2n-1

intj=i-1;//c3n-1

while(j>=0&&a[j]>key){//c4sumofti a[j+1]=a[j];//c5sumof(ti-1)

j--;//c6sumof(ti-1) }a[j+1]=key;//c7n-1

}}2.2时间复杂性计算36在最好情况下，ti=1,for1

i<n;在最坏情况下，ti

＝

i+1,for1

i<n;2.2时间复杂性计算37算法的时间复杂度

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上(n-1)次。平均来说插入排序算法的时间复杂度为O(n2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。

38复杂性分析的简化令T(N)为表示算法A的复杂性函数，若存在Ť(N)，使得LimN

(T(N)–Ť(N))/T(N)=0

那么，就可以用Ť(N)来代替T(N)，从而简化复杂性的分析。例如：T(N)=3N2+4NlogN+7，Ť(N)=3N2，则

LimN

(T(N)–Ť(N))/T(N)=LimN

4NlogN+7/3N2+4NlogN+7=039用阶来表示复杂性在渐进复杂性分析中，只要关心Ť(N)的阶就够了，不必关心Ť(N)中的常数因子，这样我们就只需要用Ť(N)的阶来表示该算法的复杂性。例如，计算一个N维矩阵A的平方的时间复杂性可估算为2N*N2=2N3，即此计算的时间复杂性为3阶。402.3时间复杂性的渐近性态时间复杂性的渐近性态：

(T(n)-t(n))/T(n)0

，asn;t(n)是T(n)的渐近性态，为算法的渐近复杂性。在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。41几个记号设f(N)、g(N)都是定义在正整数集上的函数。上界记号O：如果存在正的常数C和自然数N0，使得当N≧N0

时有f(N)≦Cg(N)，则f(N)有上界函数g(N)，记为f(N)=O(g(N))。下界记号Ω：如果存在正的常数C和自然数N0，使得当N≧N0

时有f(N)≧Cg(N)，则f(N)有下界函数g(N)，记为f(N)=Ω(g(N))。同阶记号Θ：f(N)=Θ(g(N))表示f(N)和g(N)同阶。低阶记号o：f(N)=o(g(N))表示f(N)比g(N)低阶422.3时间复杂性的渐近性态渐近上界记号OO(g(n))={f(n)|存在正常数c和n0使得对所有n

n0有：

0

f(n)

cg(n)}例如：3n-10=O(n);n2+2n+3=O(n2);3logn+loglogn=O(logn);常数=O(1)432.3时间复杂性的渐近性态大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);如果f(n)是次数为d的多项式，即f(n)=adnd+…+a1n+a0，则f(n)=O(nd)在大O符号中包含常数因子和低阶项被认为是不好的。应该用大O的最简单形式描述算法的时间复杂性。应该用大O符号尽可能接近地表征一个函数。442.3时间复杂性的渐近性态渐近下界记号

(g(n))={f(n)|存在正常数c和n0使得对所有n

n0有：0

cg(n)

f(n)}渐近确界记号⊙

当且仅当f(n)=O(g(n))且f(n)=(g(n))，定义f(n)=⊙(g(n))。表示f(n)与g(n)同阶。452.3时间复杂性的渐近性态非紧上界记号o

若对于任意正常数c>0，存在常数n0>0，当n>=n0时，满足0f(n)cg(n)，则称f(n)=o(g(n))。非紧下界记号

若对于任意正常数c>0，存在常数n0>0，当n>=n0时，满足0cg(n)f(n)，则称f(n)=

(g(n))。例如，f(n)=12n2+6n=o(n3)=(n)直观上，o(.)在渐近意义上类似于“小于”，(.)在渐近意义上类似于“大于”。462.4非递归算法分析例1：交换i和j的内容

Temp=i；i=j；j=temp；

以上三条单个语句的执行次数均为1，该算法段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=Ο(1)。472.4非递归算法分析例2：求数组最小值

int

ArrayMin(inta[],intn){min=a[0];for(i=1;i<n;i++)if(a[i]<min)min=a[i];returnmin;}

循环体内计算时间*循环次数。如果循环变量与问题规模n有关，则时间复杂度一般为O(n)。

482.4非递归算法分析例3：嵌套循环情况

(1)x=0；y=0；

(2)for(k=1；k<=n；k++)(3)x++；

(4)for(i=1；i<=n；i++)(5)for(j=1；j<=n；j++)(6)y++；

该算法段的时间复杂度为T(n)=Ο(n2)。

当有若干个嵌套循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的执行次数决定的。492.4非递归算法分析例4：嵌套循环情况for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i,j]=0;for(k=0;k<=n;++k)c[i,j]=c[i,j]+a[i,k]*b[k,j]; }该算法时间复杂度为O(n3

)50非递归算法的基本法则：顺序语句：各语句计算时间相加；for/while循环：循环体内计算时间*循环次数；嵌套循环：

最深层循环体内计算时间*所有循环次数；if-else语句：

if语句计算时间和else语句计算时间的较大者。2.4非递归算法分析512.5递归算法分析递归算法：建立递归方程;递推（迭代）求解例1：求n!int

factorial(intn){if(n==0)return1;returnn*factorial(n-1);}52îíì>+==15)2(217)(2nnnTnnT)(2nO=222112222225)2(52)2(52)1(25))2(5))4(5)8(2(2(25))2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk+×´+++=+++=++=+=--L2.5递归算法分析例2：53例线性对数阶O(log2n)：

i=1;

①

while(i<=n)

i=i*2;②解：语句1的频度是1,

设语句2的频度是f(n),

则：2^f(n)<=n;f(n)<=log2n

取最大值f(n)=log2n,

T(n)=O(log2n)54Ο(1)称为常数级Ο(logn)称为对数级Ο(n)称为线性级Ο(nc)称为多项式级Ο(cn)称为指数级Ο(n!)称为阶乘级(n为问题的规模,c为一常量)2.6算法复杂性的一般表示形式低高时间复杂性55提纲一、算法与程序二、算法复杂性分析三、用C++语言描述算法的方法56用c++描述算法57（1）选择语句：（1.1)if语句：（1.2)？语句：

if(expression)statement;elsestatement;

exp1?exp2:exp3y=x>9?100:200;等价于：

if(x>9)y=100;elsey=200;58（1.3)switch语句：switch(expression){case1:statementsequence;break;case2:statementsequence;break;

default:statementsequence;}59（2）迭代语句：（2.1)for循环：

for(init;condition;inc)statement;（2.2)while循环：

while(condition)statement;（2.3)do-while循环：

do{statement;}while(condition);60（3）跳转语句：（3.1)return语句：

returnexpression;（3.2)goto语句：

gotolabel;

label:61（4）函数：例：

return-typefunctionname(para-list){bodyofthefunction}

int

max(int

x,inty)