计算机算法概述

会计学1计算机算法概述计算机算法概述2第1页/共94页3与数据结构的区别：考虑问题的角度：数据结构关心不同的数据结构在解题中的作用和效率；算法关心不同设计技术的适用性和效率。考虑问题的高度：数据结构关心的是解具体问题，算法不仅如此，它提供一种解决问题的通用方法。高级程序设计语言（C, C+） 数据结构 算法设计与分析 第2页/共94页4 n广播操图解是广播操的算法;n菜谱是做菜的算法；n歌谱是一首歌曲的算法；n空调说明书是空调使用的算法等What？第3页/共94页5例1：给出求1+2+3+4+5的一个算法。算法1 按照逐一相加的程序进行。第一步 计算1+2,得到3；第二步 将第一步中的运算结果3与3相加,得到6；第三步 将第二步中的运算结果6与4相加,得到10；第四步 将第三步中的运算结果10与5相加,得到15。第4页/共94页6算法2 可以运用公式2) 1(321nnn直接计算;第一步 取n=5;第二步 计算2) 1( nn第三步 输出运算结果。第5页/共94页7第一步 两个野人先过河，一个野人回来； 第二步 再两个野人过河，一个野人回来； 第三步 两个牧师过河，一个野人和一个牧师回来； 第四步 两个牧师过河，一个野人回来； 第五步 两个野人过河，一个野人回来； 第六步 两个野人过河。 第6页/共94页8算法广义：在解决问题时，按照某种机械步骤一定可以得到问题结果（有解时给出问题的解，无解时给出无解的结论）的处理过程。狭义：用计算机解决问题的方法和步骤的描述。第7页/共94页920 世纪最伟大的科学技术发明-计算机；计算机是对人脑的模拟，它强化了人的思维；没有软件的支持，超级计算机只是一堆废铁而已。Why to study？第8页/共94页10现代科学研究的三大支柱理论研究科学实验科学计算研究算法第9页/共94页1121世纪信息社会的两个主要特征：“计算机无处不在”“数学无处不在”21世纪信息社会对科技人才的要求：-会“用数学”解决实际问题。-会用计算机进行科学计算。第10页/共94页12本课程为计算机科学与技术学科本科生的专业课。 How to study？通过该课程的学习，对计算机常用算法有一个全 盘的了解，掌握通用算法的一般设计方法。学会对算法的时间和空间复杂性进行分析，掌握提高算法效率的方法和途径。(评价有效算法)第11页/共94页13n问题分析：准确、完整地理解和描述问题 n数学模型建立n算法设计与选择：创造性的活动n算法表示：思想的表示形式n算法分析：算法时空特性分析n算法实现n程序调试：测试n结果整理文档编制第12页/共94页14算法概述第13页/共94页15第14页/共94页161）确定性 算法每种运算必须有确切定义，不能有二义性。 例：不符合确定性的运算： 5/0 将6或7与x相加 未赋值变量参与运算第15页/共94页174）输出 一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。5）有穷性/有限性 一个算法总是在执行了有穷步的运算之后终止。2）能行性 算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。 例：整数的算术运算是“能行”的 实数的算术运算是“不能行”的第16页/共94页18第17页/共94页19求两个正整数的最大公约数。例1.1 数学模型：m，n0 整数，求d，d能整除m，n，且m/d与n/d互质。第18页/共94页20n算法描述如下：nmain( )nint m,n,d,i;n input (m,n);n d=1； /变量d是为累乘因数而设置的；n for (i=2; i=m and i第n个学生(学生i)进行操作：操作对象：数组a，灯编号含因数i，即ai*k ；操作： ai*k = 1 - ai*k ；输出灯的开关状态。第26页/共94页28void main( ) int n,a1000,i,k; scanf(%d,&n); for( i=1;i=n;i+) ai=0; for( i=2;i=n;i+) k=1; while ( i*k = n) ai*k = 1 - ai*k; k = k + 1; for( i=1;i第n-1个(每个元素i)操作与第i+1第n元素(每个元素j)比较，若相等则标志量置0，循环中断；若flag=1，则无重复；反之，有重复。第29页/共94页31void main() int a100,i,j,flag,n; scanf(%d,&n); for (i=1;i=n;i=i+1) scanf(%d,&ai); flag = 1; for (i=1;i=n-1;i=i+1) for (j=i+1;j=n;j=j+1) if(ai=aj) flag = 0; break; if (flag = 1) printf(No repeatn); else printf(Repeatn);第30页/共94页32例1.4冒泡排序 v 排序过程 1、比较第一个记录与第二个 记录，若关键字为逆序则交换；然 后比较第二个记录与第三个记录； 依次类推，直至第 n -1 个记录和第 n 个记录比较为止，结果关键字最大的记录被安 置在最后一个记录上。 2、对前 n-1 个记录进行第二 趟冒泡排序，结果使关键字次大的 记录被安置在第 n-1 个记录位置。 3、重复上述过程，直到 “在 一趟排序过程中没有进行过交换记 录的操作” 为止。 初 始 关 键 字 49 38 65 97 76 13 27 49 第 一 趟 排 序 49 38 49 97 76 97 97 13 97 97 27 97 97 49 38 49 65 76 13 27 49 38 49 65 13 27 49 第 二 趟 排 序 38 49 13 27 49 第 三 趟 排 序 38 13 27 49 第 四 趟 排 序 13 27 38第 五 趟 排 序 第 六 趟 排 序 for ( j = 1; j ; j + +) if ( r j +1 r j ) r j r j + 1 ; for ( j = 1; j ; j + +) if ( r j +1 1; i - - ) ; while ( i 1) / while i = n ; i = k ; Void BubbleSort(SqList &L) 初 始 关 键 字 49 38 65 97 76 13 27 49 k = j ; /交换的位置 k = 1 ; 第31页/共94页33n例1.5 警察抓小偷警察局抓了a，b，c，d四名偷窃嫌疑犯，其中只有一人是小偷。审问中 a说：“我不是小偷。” b说：“c是小偷。” c说：“小偷肯定是d。” d说：“c在冤枉人。”现在已经知道四个人中三人说的是真话，一人说的是假话，问到底谁是小偷？第32页/共94页34n这种让所有可能解都进行检验，以求得真解的方法称为“枚举尝试法”，也是“蛮力法”、“暴力法” 。n为方便设计程序，将a,b,c,d将四个人进行编号，号码分别为1，2，3，4。第33页/共94页35n算法设计：用变量x存放小偷的编号，则x的取值范围从1取到4，就假设了他们中的某人是小偷的所有情况。四个人所说的话就可以分别写成：qa说的话：x1qb说的话：x=3qc说的话：x=4qd说的话：x4或not(x=4)n注意:在x的枚举过程中，当这四个逻辑式的值相加等于3时，即表示“四个人中三人说的是真话，一人说的是假话”。 if (x!=1)+(x=3)+(x=4)+(x!=4)=3)第34页/共94页36#include stdafx.hvoid main()int x;for(x=1;x=4;x=x+1)if (x!=1)+(x=3)+(x=4)+(x!=4)=3)printf(%c is a thief,char(64+x);第35页/共94页37第36页/共94页38n开始部分的元素从前向后移，容易确定；但数组中后k个元素是从后向前移，如何确定？第37页/共94页39void alg1() int a100,b100,i,n,k; scanf(%d,%d,&n,&k); for (i=0;in;i=i+1) scanf(%d,&ai); for (i=0;in;i=i+1) b(k+i) % n = ai; for (i=0;in;i=i+1) printf(%d,bi); printf(n);第38页/共94页40第39页/共94页41void alg2() int a100,i,j,n,k,temp; scanf(%d,%d,&n,&k); for (i=0;in;i=i+1) scanf(%d,&ai); for (i=0;i0;j=j-1) aj = aj-1; a0 = temp; for (i=0;in;i=i+1) printf(%d,ai); printf(n);第40页/共94页42n1）一组循环移动的情况：n通过计算我们可以确定某个元素移动后的具体位置，如n=5, k=3时：0、1、2、3、4循环移3位后为2、3、4、0、1。可通过计算得出0移到3的位置，3移到1的位置，1移到4的位置，4移到2的位置，2移到0的位置；一组移动（0-3-1-4-2-0）正好将全部数据按要求进行了移动。这样只需要一个辅助变量，每个数据只需一次移动就可完成整个移动过程。n如果算法就这样按一组移动去解决问题，就错了。因为还有其它情况。第41页/共94页43n循环移动的组数，与k、n是怎么样的关系呢？n我们再看一个例子，当N=6，K=2时， 0、1、2、3、4、5经移动的结果是4、5、0、1、2、3。 0移到2的位置，2移到4的位置，4移到0的位置，一组移动完成了3个数据的移动，接下来，还有一组1-3-5-1。共进行二组循环移动，就能将全部数据移动完毕。第42页/共94页44第43页/共94页45void alg3() int a100,b0,b1,i,j,n,k,m,tt; scanf(%d,&n); scanf(%d,&k); for(i=0;in;i=i+1) scanf(%d,&ai); m=gcd(n,k); for(j=0;jm;j=j+1) b0=aj; tt=j; for(i=0;in/m;i=i+1) tt=(tt+k) % n; b1=att; att= b0; b0=b1; for(i=0;in;i=i+1) printf(%d,ai); printf(n);第44页/共94页46第45页/共94页47第46页/共94页48主要缺点： 使算法设计人员过早考虑算法控制流程，而不去考虑全局结构，不利于逐步求精。 随意性太强，结构化不明显。 不易表示数据结构。 层次感不明显。NYr等于0?输出n的值输入正整数m和n开始结束m n; n rrm被n除的余数rm被n除的余数第47页/共94页49（2）主要缺点： 不易扩充和修改，不易描述大型复杂算法。输入正整数m和n rm被n除的余数 m n; n rrm被n除的余数 当r不等于 0输出n的值 第48页/共94页504 PAD图 问题分析图(Problem Analysis Diagram, 简称PAD)表示的算法是一个二维树形结构图，层次感强、嵌套明确且有明确的控制流程。第49页/共94页51问题分析图实例第50页/共94页52第51页/共94页53第52页/共94页54第53页/共94页55第54页/共94页56第55页/共94页57第56页/共94页58时间复杂性和空间复杂性为什么要考虑时间复杂性？第57页/共94页59考虑程序的空间复杂性的理由：第58页/共94页60第59页/共94页61第60页/共94页62估算执行时间的方法 选择一种或多种（如加、乘和比较等），然后确定这种（些）操作分别执行了多少次。令n代表程序实例特征，则执行时间计算公式为：TP（n）= c1ADD(n) + c2SUB(n) + c3MUL(n) + c4DIV(n)+c1、c2、c3、c4分别表示一次加、减、乘、 除操作所需的时间。函数ADD (n) 、SUB (n) 、MUL (n) 、DIV (n)分别表示程序P中，所使用的加、减、乘、除操作的次数。这种方法是否成功取决于识别关键操作的能力，这些关键操作对时间复杂性的影响最大。一条语句在整个程序运行时实际执行时间= 频率计数 * 每执行一次该语句所需的时间第61页/共94页63第62页/共94页64第63页/共94页65第64页/共94页66第65页/共94页67第66页/共94页68N0f(N)g(N)当说一个算法具有O(g(n)的计算时间时，指的就是如果此算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于g(n)的一个常数倍。g(n)是计算时间f(n)的一个上界函数，f(n)的数量级就是g(n)。第67页/共94页69第68页/共94页70第69页/共94页71第70页/共94页72第71页/共94页73结论：在顺序处理机上扩大所处理问题的规模，最有效的途径是降低算法计算复杂度的数量级，而不是（仅仅依靠）提高计算机的速度。第72页/共94页74第73页/共94页75n定义1.2 若存在两个正常数C和自然数N0，使得当N N0时有|f(N)|C|g(N)|，则称函数f(N)当N充分大时下有界；且g(N)是它的一个下界，记为f(N)=(g(N)。这时我们说f(N)的阶不低于g(N)的阶。第74页/共94页76第75页/共94页77“平均情况”限界函数第76页/共94页78第77页/共94页79第78页/共94页80【例1.7】交换i和j的内容。 Temp=i； i=j； j=temp； 以上三条单个语句的频度均为1，该算法段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=(1)。 如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是(1)。 第79页/共94页81【例1.8】循环次数直接依赖规模n变量计数之一。 (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)。 当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。第80页/共94页82【例1.9】循环次数间接依赖规模n-变量计数之二。 (1) x=1； (2) for(i=1；i=n；i+) (3) for(j=1；j=i；j+) (4) for(k=1；k=0 and Aik ) (3) i=i-1； (4) return i； 此算法的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及k的取值有关： 1. 若A中没有与k相等的元素，则(2)频度f(n)=n(最坏情况)； 2. 若A最后一个元素等于k ，则(2)频度f(n)是常数1(最好情况);第82页/共94页84 在求平均情况时，一般地假设查找不同元素的概率P是相同的,则算法的平均复杂度为： 若对于查找不同元素的概率P不相同时，其算法复杂度就只能做近似分析，或在构造更好的算法或存储结构后，做较准确的分析。第83页/共94页85【例1.11】求N！ 构造算法中的两个步骤： 1）N!=N*(N-1)！(n1) 2）0!=1， 1!=1(n=0,1)。 递归算法如下： 以n=3为例，调用过程如下： fact(3)-fact(2)-fact(1)-fact(2)-fact(3) 递 归 回 溯 n递归算法分析第84页/共94页86【例1.11】求N！ 递归方程为： T(n)=T(n-1)+O(1) 其中O(1)为一次乘法操作。 迭代求解过程如下： T(n)=T(n-2)+O(1)+O(1) =T(n-3)+O(1)+O(1)+O(1) =O(1)+O(1)+O(1)+O(1) =n*O(1) =O(n)第85页/共94页87【例1.12】抽象地考虑以下递归方程，且假设n=2k，则迭代求解过程如下： T(n) =O(n) 第86页/共94页88【例1.13】一个楼有n个台阶，有一个人上楼有时一次跨一个台阶，有时一次跨两个台阶，编写一个算法，计算此人有几种不同的上楼方法，并分析算法的时间复杂度。 解：设计一个递归算法。 H(int n) if (n2 T(n) 2T(n-1) 2 T(n-2) 2 T(1) =O(2 )2n-1n第87页/共94页89【例1.14】抽象地考虑以下递归方程，且假设n=2k，则迭 代求解过程如下： T(n)=2T(n/2)+O(n) =2T(n/4)+2O(n/2)+O(n) = =O(n)+O(n)+ +O(n)+O(n)+O(n) =kO(n) =O(kn) =O(nlog2 n) 第88页/共94页90【例1.15】抽象地考虑以下递归方程，迭代求解过程如下： T(n)=T(n/3)+T(2n/3)+n =T(n/9)+T(2n/9)+n/3+T(2n/9)+T(4n/9)+2n/3 = n=(k+1)n=n(log n+1)i=0k2/3nn/3n/92n/92n/34n/92n/9设最长路径长度为k，(2/3) n=1k=log nk2/3 T(n) =O(nlog n)2/3第89页/共94页91 首先要提醒大家，不要一味地追求算法的效率，应当在满足正确性、可靠性、健壮性、可读性等质量因素的前提下，设法提高算法的效率。 看两组操作： (1) a=a+b； b=a-b；a=a-b； (2) t=a； a=b； b=t； 两组操作的功能都是：“交换变量a、b中的数据”。虽然第一组操作节省了一个存储空间，但失去了可读性，是不可取的。第90页/共94页92 下面给出一些原则上的建议：a.保证正确性、可靠性、健壮性、可读性 1）当心视觉上不易分辨的操作符发生书写错误。 2）算法中的变量(指针、数组)在被引用前，一定要有确切 的含义，或是被赋值或是经模块接口传递信息。 3）算法中要当心变量发生上溢或下溢(数组的下标越界)。 4）写算法时就要考虑可能出现错误的情况，提示执行错 误处理算法。 5）编写算法时区别问题的循环条件和停止条件，不要误用。 6）注意算法中循环体或条件体的位置，不要误把循环体 内的操作写在循环体外或者出现相反错误。第91页/共94页93b提高效率1）以提高算法的全局效率为主，提高局部效率为辅。 2）在优化算法效率时，应先找出限制效率的“瓶颈”。 3）多数情况下，时间效率和空间效率可能是对立的，此 时应分析哪个更重要，作适当折衷。 4）可考虑先选取合适的数据结构，再优化算法。 5）递归过程的实现决定了递归算法的效率往往很低，费 时和费内存空间。在解决问题时，如果能用递推法解 决的，应考虑用递推法，其效率更高些。 6）注意多用数学知识，可以大大提高算法效率。 7）细节上的问题,如:乘、除运算效率比加、减运算低。 第92页/共94页94第93页/共94页