算法引论及简单算法

算法引论及简单算法第1页，课件共37页，创作于2023年2月2注意算法是程序设计的灵魂第2页，课件共37页，创作于2023年2月3与数据结构的区别：考虑问题的角度：数据结构关心不同的数据结构在解题中的作用和效率；算法关心不同设计技术的适用性和效率。考虑问题的高度：数据结构关心的是解具体问题，算法不仅如此，它提供一种解决问题的通用方法。与其他课程的关系高级程序设计语言（C语言，等）数据结构算法设计与分析系统的设计与实现第3页，课件共37页，创作于2023年2月4主要内容目标：了解算法分析的基本含义。掌握查找算法、排序算法、递推算法等算法理念。提纲补1.1算法分析补1.2查找算法补1.3排序算法补1.4递推算法第4页，课件共37页，创作于2023年2月5补1.1算法分析前面的课程内容以C语言语法为主本补充章介绍一些基本算法大家在编写程序的时候，“八仙过海，各显神通”，解决同一个问题，可以使用各种方法。算法之间存在着“优劣”之分第5页，课件共37页，创作于2023年2月6补1.1算法分析1、算法分析的目的

通过对算法分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好算法，改进差算法，避免无益的人力和物力浪费。第6页，课件共37页，创作于2023年2月7补1.1算法分析2、算法分析的含义算法分析是一种分析技术，它以独立于具体的硬件平台、编译器和编程语言的方式，来描述算法的执行行为，即它关心的是算法，而不是程序。算法分析是一种测量算法的性能的方法，它不关心精确的细节，如在算法的某次运行中总共执行了多少条机器指令，而是想要一个大致的估计，即随着输入数据规模的增大，算法所需工作量以何种速度递增。（关心变化趋势）第7页，课件共37页，创作于2023年2月8补1.1算法分析3、算法复杂性时间复杂性和空间复杂性第8页，课件共37页，创作于2023年2月9补1.1算法分析1.有些计算机需要用户提供程序运行时间的上限，一旦达到这个上限，程序将被强制结束。2.正在开发的程序可能需要提供一个满意的实时响应。为什么要考虑时间复杂性？第9页，课件共37页，创作于2023年2月101.多用户系统中运行时，需指明分配给该程序的内存大小。2.可提前知道是否有足够可用的内存来运行该程序。3.一个问题可能有若干个内存需求各不相同的解决方案，从中择取。4.利用空间复杂性来估算一个程序所能解决问题的最大规模。考虑程序的空间复杂性的理由：补1.1

算法分析第10页，课件共37页，创作于2023年2月114.

如何进行算法分析？事前分析：就算法本身，通过对其执行性能的理论分析，得出关于算法特性——时间和空间的一个特征函数（Ο）——与计算机软硬件没有直接关系。事后测试：将算法编制成程序后放到计算机上运行，收集其执行时间和空间占用等统计资料，进行分析判断——直接与物理实现有关。补1.1算法分析第11页，课件共37页，创作于2023年2月121）事前分析目的：试图得出关于算法执行特性的一种形式描述，以“理论上”衡量算法“好坏”。如何给出反映算法执行特性的描述？最直接方法：统计算法中各种运算的执行情况：

运用了哪些运算每种运算被执行的次数该种运算执行一次所花费的时间

算法的执行时间=∑Fi*ti补1.1

算法分析第12页，课件共37页，创作于2023年2月13估算执行时间的方法

选择一种或多种（如加、乘和比较等），然后确定这种（些）操作分别执行了多少次。令n代表程序实例特征，则执行时间计算公式为：TP（n）=c1ADD(n)+c2SUB(n)+c3MUL(n)+c4DIV(n)+···c1、c2、c3、c4分别表示一次加、减、乘、除操作所需的时间。函数ADD(n)、SUB(n)、MUL(n)、DIV(n)分别表示程序P中，所使用的加、减、乘、除操作的次数。这种方法是否成功取决于识别关键操作的能力，这些关键操作对时间复杂性的影响最大。一条语句在整个程序运行时实际执行时间=

频率计数*每执行一次该语句所需的时间补1.1

算法分析第13页，课件共37页，创作于2023年2月14频率计数：算法中语句或运算的执行次数。

例：

x=x+yfor(i=1;i<=n;i++)for(i=1;i<=n;i++)x=x+y;for(j=1;j<=n;j++)x=x+y;(a)(b)(c)

分析：

(a)：x=x+y执行了1次

(b)：x=x+y执行了n次

(c)：x=x+y执行了n2次注：在事前分析中，只限于确定与所使用机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。补1.1算法分析第14页，课件共37页，创作于2023年2月15数量级语句的数量级：语句的执行频率。例：1，n，n2

算法的数量级：算法包含所有语句的执行频率之和。算法的数量级从本质上反映了一个算法的执行特性。例：求解同一问题的三个算法分别具有n,n2,n3数量级。若n=10，则可能的执行时间将分别是10，100，1000个单位时间——与环境因素无关。补1.1算法分析第15页，课件共37页，创作于2023年2月16补1.1算法分析5、算法复杂性的等级常量阶时间复杂度为O(1)算法运行时间不随着问题的规模而变化如：简单的赋值语句，x=y;算术运算，x=y*5+z%3;固定次数的循环语句等for(i=0;i<10;i++)for(j=0;j<20;j++)a[i][j]=0;第16页，课件共37页，创作于2023年2月17补1.1算法分析线性阶时间复杂度为O(n)算法运行时间随着问题的规模而成线性变化for(i=0;i<n;i++)sum=sun+i;算法执行了多少次运算？i=0;执行了1次i<n;执行了n+1次i++；执行了n次sum=sun+i;执行了n次共执行了3n+2次运算时间复杂度就是O（3n+2）实际上，算法的时间复杂度并不精确计算基本操作的执行次数，它主要考虑问题规模的增长率。O（n）第17页，课件共37页，创作于2023年2月18补1.1

算法分析平方阶时间复杂度为O(n2)算法运行时间随着问题的规模而成平方变化for(i=0;i<n;i++){

for(j=0;j<n;j++) { sum=sun+a[i][j];//执行n2次

} printf(“%dn”,sum);//执行n次}时间复杂度就是O（n2）第18页，课件共37页，创作于2023年2月19补1.1

算法分析多项式阶时间复杂度为O(nd)d为固定常数算法运行时间随着问题的规模而成d次多项式阶变化对数阶O(logn)指数阶O(log2n)阶乘阶O(n!)………若T(n)=adnd+…+a1n+a0是一个d次多项式，则有T(n)=O(nd)第19页，课件共37页，创作于2023年2月205、算法分类（计算时间）多项式时间算法：可用多项式（函数）对其计算时间限界的算法。

常见的多项式限界函数有：

Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)指数时间算法：计算时间用指数函数限界的算法

常见的指数时间限界函数：

Ο(2n)<Ο(n！)<Ο(nn)

说明：当n取值较大时，指数时间算法和多项式时间算法在计算时间上非常悬殊。补1.1算法分析第20页，课件共37页，创作于2023年2月21

计算时间的数量级对算法有效性的影响数量级的大小对算法的有效性有决定性的影响。例：假设解决同一个问题的两个算法，它们都有n个输入，计算时间的数量级分别是n2和nlogn。则：

n=1024：分别需要1048576和10240次运算。

n=2048：分别需要4194304和22528次运算。分析：在n加倍的情况下，一个Ο(n2)的算法计算时间增长4倍，而一个Ο(nlogn)算法则只用两倍多一点的时间即可完成。补1.1

算法分析第21页，课件共37页，创作于2023年2月22典型的计算时间函数曲线结论：在顺序处理机上扩大所处理问题的规模，最有效的途径是降低算法计算复杂度的数量级，而不是（仅仅依靠）提高计算机的速度。补1.1

算法分析第22页，课件共37页，创作于2023年2月23补1.2查找算法所谓查找（search），即根据给定的某个值，在一组数据（如一个数组）中，确定有没有出现相同值得数据元素。查找是非常实用的算法。如，查找字典。问题描述，令b表示被查找的数组，n表示数组元素的个数，x表示被查找的目标。问题是“数据x是否出现在数组b当中？”第23页，课件共37页，创作于2023年2月24补1.2查找算法1、顺序查找方法基本思路：从数组b的第一个元素开始，逐个地与x进行比较，一直到查找成功或者所有的数组元素都已经处理完毕。参考程序：intsearch(intb[],intn,intx){intk;for(k=0;(k<n)&&(b[k]!=x);k++)if(k<n)return(k);elsereturn(-1);}算法的复杂度为O(n)第24页，课件共37页，创作于2023年2月25补1.2查找算法2、折半查找方法(对于有序数组)参考程序：intsearch(intb[],intn,intx){intL,R,mid;L=0;R=n-1;while(L<=R){mid=(L+R)/2;if(x==b[mid])return(mid); elseif(x<b[mid])R=mid-1;elseL=mid+1;}return(-1);}算法的复杂度为O(lnN)第25页，课件共37页，创作于2023年2月26补1.3

排序算法所谓排序（sort），就是将一个任意的数据元素的序列，重新排列成一个具有某种顺序的序列。排序是非常实用的算法。如，成绩排名等。问题描述，令a表示待排序的数组，n表示数组元素的个数，在排序之前，数组中元素是随机的，而在排序之后，这些数据按照一定的规律存放。第26页，课件共37页，创作于2023年2月27补1.3

排序算法冒泡法基本思路：其原理为从a[0]开始，依次将其和后面的元素比较,若a[0]>a[i]，则交换它们，一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理，即完成排序。

voidbubble(int*a,intn)/*定义两个参数：数组首地址与数组大小*/{inti,j,temp;

for(i=0;i<n-1;i++)for(j=i+1;j<n;j++)/*注意循环的上下限*/if(a[i]>a[j]){temp=a[i];a[i]=a[j];a[j]=temp;}}第27页，课件共37页，创作于2023年2月28补1.3

排序算法选择法

基本思路：选择法循环过程与冒泡法一致，它还定义了记号k=i,然后依次把a[k]同后面元素比较，若a[k]>a[j],则使k=j.最后看看k=i是否还成立，不成立则交换a[k],a[i],这样就比冒泡法省下许多无用的交换，提高了效率。voidchoise(int*a,intn){ inti,j,k,temp; for(i=0;i<n-1;i++){ k=i;/*给记号赋值*/ for(j=i+1;j<n;j++) if(a[k]>a[j])k=j;/*是k总是指向最小元素*/ if(i!=k){/*当k!=i是才交换，否则a[i]即为最小*/ temp=a[i]; a[i]=a[k]; a[k]=temp; } }}第28页，课件共37页，创作于2023年2月29补1.4

递推算法递推（RecursiveAlgorithm），即从某个一直得初始条件出发，根据这个已知的事实，并按照一定规律推断出下一个事实。然后再从这个新的已知的事实出发，向下再推断一个事实。递推是计算机数值计算的一个重要方法，可以将复杂的运算简化为若干个重复的简单运算，从而发挥计算机长于重复处理的特点。其实质与差分方程类似，著名的例子为Fibonacci数列。第29页，课件共37页，创作于2023年2月30补1.4

递推算法例：猴子吃桃有一只小猴子，有一天摘了一堆桃子，当天吃掉了一半，后来觉得不过瘾，就又多吃了一只。第二天，小猴子又将剩下的桃子吃掉了一半，并多吃了一个。以后每天都吃了前一天剩下的一半零一个。到了第十天的时候，发现只剩下一只桃子了。请问小猴子第一天一共摘了多少桃子？第30页，课件共37页，创作于2023年2月31补1.4

递推算法解题思路T10=T9-T9/2-1即T9=(T10+1)*2T8=(T9+1)*2T7=(T8+1)*2……

……T1=(T2+1)*2定义A为桃子的个数，第10天为1个，第9天为4个，第8天为10个。。。。。#include<stdio.h>voidmain(){intA,i;A=1;for(i=9;i>=1;i--)A=(A+1)*2

pintf("小猴子第一天共摘了%d个桃子.\n"，A);}第31页，课件共37页，创作于2023年2月32补1.4

递推算法例：猴子分桃1979年李政道去中国科技大学访问，出了一道题目。5只猴子摘了一堆桃子，等第二天再来分。夜里一只猴子偷偷爬起来，吃掉了一只桃子，然后把剩下的桃子分成5份，取走了自己应得到的一份，然后回家了。过了会儿，第二只猴子也爬了起来，吃掉了一只桃子，然后把剩下的桃子分成5份，取走了自己应得到的一份。第三、四、五只猴子都是这样，吃掉了一只桃子后，正好把剩下的桃子每次都能分成5份。请问最初至少有多少个桃子？每只猴子夜里起床后看到多少只桃子？第32页，课件共37页，创作于2023年2月33补1.4

递推算法解题思路定义peach[i]（1≤i≤5）表示第i只猴子看到的桃子数。peach[2]=(peach[1]-1)*4/5peach[i]=(peach[i-1]-1)*4/5（2≤i≤5）

如果知道了peach[1]或者peach[5]中的任意一个，都可以递推出来每只猴子看到的桃子个数。可惜不知道啊。第33页，课件共37页，创作于2023年2月34补1.4

递推算法解题思路但是我们知道：peach[1]%5=1；peach[2