计算机科学导论 课件 第4章 算法思维

第4章算法思维ALGORITHMICTHINKING算法分析03本章目录01

什么是算法02算法实现01什么是算法什么是算法01

假设某商场销售的某种商品单价25元，每年可销售3万件。设该商品每件提价1元，则销售量减少0.1万件。如果要使总销售收入不少于75万元，求该商品的最高提价。如何让你用计算机进行求解，你怎么做？什么是算法01如何让你用计算机进行求解，你怎么做？旅行推销员问题TSP：假设你计划要进行一次旅行推销，有几个城市是你要穿越的地方。要求：

——所走路程最短

——每个城市只能访问一次

——从某城市出发，最后回到该城市什么是算法011、算法的基本定义程序=算法+数据结构1984年图灵奖获得者、Pascal之父及结构化程序设计的首创者、瑞士计算机科学家尼克劳斯·沃斯（NicklausWirth）程序：为刻画和解决现实世界的问题，在数据的某些特定的表示方式和结构的基础上对抽象算法的具体表述。---代码数据结构：现实世界的数据模型算法是一个有穷规则的集合，它用规则规定了解决特定类型问题的运算序列，或者规定了任务执行或问题求解的一系列步骤。01算法特征有穷性（可终止性）确定性输入输出能行性算法必须在有限的操作步骤内以及合理的时间内执行完成。明确的开始和结束算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。①算法中每一个步骤必须能够实现，如不允许分母为0。②算法执行结果要能够达到预期的目的，实现预定的功能。算法有0个或多个输入。什么是算法2、算法的特征算法有1个或多个输出。02算法实现02算法算法策略数学建模数据结构控制结构程序设计算法正确性与复杂性问题问题的求解算法实现02算法实现一、数学建模数学建模：用数学语言描述实际现象的过程，即建立数学模型的过程。数学模型：对实际问题的一种数学表述，是关于部分现实世界为某种目的的一个抽象的简化的数学结构。旅行推销员问题TSP：假设你计划要进行一次旅行推销，有几个城市是你要穿越的地方。要求：

——所走路程最短

——每个城市只能访问一次

——从某城市出发，最后回到该城市02数字编号代替城市名，编号之间线段长度用城市之间的距离描述算法实现路线1：

→

→

→

→

→

→①

路线总距离：1640公里路线2：①→③→④→⑥→⑤→②→①

路线总距离：1550公里

路线3：

→

→

→

→

→

→

路线总距离：1640公里不同路线的结果02算法实现

旅行推销员问题是图论中最著名的问题之一，即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。02算法实现二、算法策略蛮干/遍历遍历算法求解TSP问题：列出每一条可供选择的路线，计算出每条路线的总里程，最后从中选出一条最短的路线。所有路径组合及其长度蛮干/遍历策略会带来怎样的问题？组合爆炸路径组合数目：(n-1)!20个城市，遍历总数1.216×1017计算机以每秒检索1000万条路线的计算速度，需386年。2001年解决了德国15112个城市的TSP问题，使用了美国Rice大学和普林斯顿大学之间互连的、速度为500MHz

的CompaqEV6Alpha处理器组成的110台计算机，所有计算机花费的时间之和为22.6年。02算法实现TSP问题，有没有其他求解算法呢？最优解

vs.可行解不同的算法设计策略：遍历、搜索算法分治算法贪心算法动态规划算法……算法策略可行解最优解TSP问题的可行解与最优解示意贪心算法是一种算法策略。基本思想“今朝有酒今朝醉”:一定要做当前情况下的最好选择，否则将来可能会后悔，故名“贪心”。从某一个城市开始，每次选择一个城市，直到所有城市都被走完。每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距离最短。02童年时，大人给小孩讲故事：从前有座山，山上有个庙，庙里有个老和尚和小和尚，老和尚给小和尚讲故事，讲的是：从前有座山，山上有个庙，……。算法实现递归的典型听觉和视觉形式---自相似性事物的无限重复性构造递归与迭代02算法实现递归与迭代求n!的算法或程序--用迭代和递归方法构造有什么不同？02算法实现longintFact(intn){intcounter；

longproduct=1;forcounter=1tonstep1{product=product*counter；}/*迭代*/returnproduct;} CounterProduct初始值1

Fact(5)的执行过程【示例】求n!的算法或程序--用迭代方法构造：循环-替代-递推循环第1次 1 1循环第2次 2 2循环第3次 3 6循环第4次 4 24循环第5次 5 120退出循环 6 12002算法实现longintFact(intn){longintx; If(n>1){x=Fact(n-1);/*递归调用*/returnn*x;}elsereturn1;/*递归基础*/}n>1返回结果1X=Fact(n-1)NY返回结果n*X开始结束传进的参数nFact(n)

【示例】求n!的算法或程序--用递归方法构造：函数调用运用递归进行程序构造：函数结构，自身调用自身，高阶调用低阶02算法实现n>1返回结果1X=Fact(n-1)NY返回结果n*X开始结束传进的参数nn>1返回结果1X=Fact(n-1)NY返回结果n*X开始结束传进的参数nn>1返回结果1X=Fact(n-1)NY返回结果n*X开始结束传进的参数nn>1返回结果1X=Fact(n-1)NY返回结果n*X开始结束传进的参数nFact(4)4返回4!=24Fact(3)返回3!=624Fact(2)返回2!=2Fact(1)返回1!=13622114

63

22

112602算法实现h(0)h(n+1)h(0)h(n+1)寻找路径沿路径计算沿一致路径计算h(0)h(n+1)可能计算路径并不同迭代/递推递归通常，只能由函数结构实现在前次结果基础上进行计算可采用循环结构实现02算法实现伪代码表达算法：Begin

输入变量x，y；ify=0then输出错误提示else

z=x/y输出zEndif;End自然语言表达算法：开始输入变量x，y；判断y是否为0；如果y=0，则输出错误提示；否则计算z=x/y；输出z。结束优点：简单，便于阅读。缺点：文字冗长，容易出现歧义。

伪代码没有标准，用类似自然语言形式表达。伪代码结构清晰、代码简单、可读性好。算法的表示—控制结构02算法分析03算法思维：复杂度算法复杂度：求解问题的某一个算法的复杂性，反映了一个算法的效率。通常需要考虑算法执行时所需要的计算机资源。时间复杂度：衡量算法运行速度。空间复杂度：衡量算法运行中所占存储空间的大小。算法分析03算法分析1、时间复杂度的表示问题求解算法通常与问题规模n相关，一个算法由一些基本步骤组成，则算法基本步骤执行的次数表达为关于n的函数T(n)，称为时间复杂度。时间复杂度是衡量算法的运行时间随着问题规模的增大而增加的趋势，而不是具体的运行时间。算法时间复杂度常用大O表示（读为：大圈，Order，big-O）。大O表示法：O(T(n))【例】

求下面算法时间复杂度

temp=i;i=j;j=temp;以上语句的频度均为1，程序执行时间是与问题规模n无关的常数。算法时间复杂度为常数阶时，记作T(n)=O(1)。如果算法执行时间不随问题规模n的增加而增长，即使算法有上千条语句，其执行时间也是一个较大的常数。032、算法时间复杂度计算案例算法分析【例】求下面算法时间复杂度

(1)(2)(3)(4)(5)a=0;b=1;for(i=2;i<=n;i++){s=a+b;b=a;a=s;}/*计算频度=2次*//*计算频度=n次*//*计算频度=n-1次*//*计算频度=n-1次*//*计算频度=n-1次*/03算法时间复杂度为：T(n)=2+n+3(n-1)=4n-1=O(n)(1)(2)(3)(4)sum=0；for(i=1;i<=n;i++)for(j=1;j<=n;j++)sum++;/*计算频度=1次*//*计算频度=n+1次*//*计算频度=n（n+1）次*//*计算频度=n2次*/算法时间复杂度为：T(n)=2n2+2n+2=O(n2)算法分析033、不同量级复杂性在计算时间方面的差异算法分析03冒泡排序快速排序算法分析03冒泡排序是通过交换相邻两个元素实现的思想：比较相邻2个元素，如果次序不对，则将2个元素位置互换，依次由上往下比较，最终较大（或较小）的元素向上浮起，犹如冒泡。算法分析03951426951426951462951642956142965142第一趟：对6比较算法分析03951426965142965412965421第一趟第二趟第三趟fori=1ton-1forj=1ton-iifA[j]>A[j+1]swap(A[j],A[j+1])冒泡排序的时间复杂度？在完全有序的情况下，最好的时间复杂度是O(n)，1次冒泡。在极端情况完全逆序，时间复杂度为O(n2)(n-1)+(n-2)+…+1=n(n-1)/2算法分析03快速排序的基本思想是：

（1）从列表中取出一个元素作为“基准数”。

（2）比基准数大的元素放到它的右边；

小于基准数的元素放到它的左边；

相同的数可以放在任一边。

退出分区后，基准数处于列表中间位置。

（3）利用递归算法对小于基准数的元素排序；

然后对大于基准数的元素排序。（4）递归结束条件是列表长度小于等于1；

当列表长度=0或1时，排序完成。算法分析03循环状态排序元素列表说

明初始状态61279345108初始序列，以6为基准数第1轮31254697108基准数6归位第2轮31254

以3为基准数

21354

基准数3归位第3轮21

以2为基准数

12

基准数2归位第4轮1

只有1位，无需排序第5轮

54

以5为基准数

45

基准数5归位第6轮

4

只有1位，无需排序第7轮

97108以9为基准数

87910基准数9归位第8轮

87

8为基准数，

78

基准数8归位第9轮

7

7只有1位，无需排序第10轮

1010只有1位，无需排序循环结束12345678910排序完成算法分析03复杂度：快速排