数据分析与算法设计分析基础

1、数据分析与算法设计1：算法分析基础信电学院信通所wangli副研究员(645840)浙江大学玉泉校区信电楼505室课程简介数据分析与算法设计 数据结构 + 算法 + 数值分析本课程的重要程度the core of computer science计算机科学与技术专业必修技能程序员求职笔试、面试必考内容本课程的特色结合实战！中英文混合直击面试和参考书本课程配套其他经典参考书课程成绩组成课堂表现占10%：包括到课情况、发言 随机点名3%+3%，抢答1%/次，0.5% /次课程作业占30%：包括课后习题、编程作业习题7%+7%，研讨8%，小作业8%成绩占60%：期末卷面成绩60%课程资源FTP地址：

2、5端口：21用户名：algorithms： algorithms教学大纲、PPT、习题、MIT教学等课程正式开始主要内容绪论算法算法问题求解基础重要类型基本数据结构算法效率分析基础分析框架渐近符号和基本效率类型非递归算法的数学分析 递归算法的数学分析主要内容绪论算法算法问题求解基础重要类型基本数据结构算法效率分析基础分析框架渐近符号和基本效率类型非递归算法的数学分析 递归算法的数学分析算法？算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。proble

3、malgorithmoutputinput“computer”同一问题-不同算法不同的算法可能用不同的时间、空间或效率来完成同样的任务。范例：求解最大公约数Problem:Find(m,n),thegreatestcommon egers mdivisor of two nonnegative, not both zero and nExles:(60,24) = 12求解最大公约数：方法一方法一：辗转相除法（最出名、历史最悠久）Euclids Algorithm首次出现于几何原本（约公元前300年）古希腊数学家欧几里德Euclids algorithm is based on repeate

4、d application of equality(m,n) = until the second numbertrivial.(n, m mod n)es 0, whiakes the problemwhile n 0 dor m mod n m nn rreturn mExle:(60,24) =(24,12) =(12,0) = 12求解最大公约数：方法二方法二：连续整数检测法Consecutiveeger checking algorithmStep 1Step 2Assign the value of m,n to tDivide m by t. If the remainder i

5、s 0, go to Step 3; otherwise, go to Step 4Divide n by t. If the remainder is 0, return t and stop; otherwise, go to Step 4Decrease t by 1 and go to Step 2Step 3Step 4求解最大公约数：方法三方法三：质因数分解法把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的最大公约数。例如：求24和60的最大公约数先分解质因数，得24=2223，60=223524与60的全部公有的质因数是2、2、3，它们的积是

6、223=12(24, 60)=12。所以，Is thisgorithm?Sieve of Eratosthenes 埃拉托色尼筛选法：“算法”与“方法”的区别?比如我提出一种新的分类的方法，如何才能称之为算法，或者称之为方法？算法和方法的区别（个人观点）对于一个给定的problem（问题），method是一种解决问题的思路，只需给出一个大致的流程，而具体每一步怎么做可以有很多变化，这个词的粒度比较大。同一method下可以包含多个时间和空间复杂度都不同（甚至相差很大）的 algorithm。而algorithm则是要给出每一步的具体步骤，可以方便的转化成计算机代码。这个词的粒度比 method

7、要细很多，但仍具有一定程度的灵活性，可以包含几个不同时空复杂度的变种。主要内容绪论算法算法问题求解基础重要类型基本数据结构算法效率分析基础分析框架渐近符号和基本效率类型非递归算法的数学分析 递归算法的数学分析算法问题求解基础理解问题精确解或近似解选择数据结构算法设计策略设计算法证明正确性分析算法设计程序主要内容绪论算法算法问题求解基础重要类型基本数据结构算法效率分析基础分析框架渐近符号和基本效率类型非递归算法的数学分析 递归算法的数学分析重要类型排序 sorting查找 searching字符串处理 string prosing图问题 graroblems组合问题 combinatorial

8、problems几何问题 geometric problems数值问题 numerical problems主要内容绪论算法算法问题求解基础重要类型基本数据结构算法效率分析基础分析框架渐近符号和基本效率类型非递归算法的数学分析 递归算法的数学分析基本数据结构list栈数组 array链表 linked list字符串 stringstack队列 queue优先队列 priority queue图 graph树 tree堆集合与字典 set and dictionary主要内容绪论算法算法问题求解基础重要类型基本数据结构算法效率分析基础分析框架渐近符号和基本效率类型非递归算法的数学分析 递归算法

9、的数学分析算法效率的度量方法设计算法要尽量地提高效率，这里效率高一般指的是算法的执行时间。那么如何来度量一个算法的执行时间呢？所谓“是骡子是马拉出来遛遛”，比较容易想到的方法就是把算法跑若干次，然后拿个“计时器”在旁边计时。这种事后统计方法看上去的确不错，并且也并非真的要你拿个计时器在那里计算，因为计算机都有计时功能。算法效率的度量方法事后统计方法：这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。但这种方法显然是有很大缺陷的：必须依据算法事先编制好测试程序，通常需要花费大量时间和精力，完了发觉测试的是糟糕的算法，那不是功

10、亏一篑？赔了娘子又折兵？不同测试环境差别不是一般的大！算法效率的度量方法把刚刚的估算方法称为事后诸葛亮。的计算机前辈们也不一定知道诸葛亮是谁，为了对算法的评判更为科学和便捷，他们研究出事前分析估算的方法。事前分析估算方法：在计算机程序编写前，依据统计方法对算法进行估算。经过总结，发现一个高级语言编写的程序在计算机上运行时所消耗的时间取决于下列：算法效率的度量方法1. 算法采用的策略、方案2. 编译产生的代码质量3. 问题的输入规模4. 机器执行指令的速度由此可见，抛开这些与计算机硬件、有关的，一个程序的运行时间依赖于算法的好坏和问题的输入规模。（所谓入量的多少）输入规模是指输用高斯先生的那个求

11、和算法来跟大家谈谈：算法效率的度量方法第一种算法：i, sum = 0, n = 100;/ 执行1次for( i=1; i = n; i+ )sum = sum + i;第二种算法：/ 执行了n+1次/ 执行n次sum = 0, n = 100;sum = (1+n)*n/2;/ 执行1次/ 执行1次算法效率的度量方法第一种算法执行了1+(n+1)+n=2n+2次。第二种算法，是1+1=2次如果把循环看做一个整体，忽略头尾判断的开销，那么这两个算法其实就是n和1的差距。有些喜欢跟真理死磕的朋友可能对这观点意见不是一般的大！因为循环判断在算法1里边执行了n+1次，看起来是个不小的数量，凭什么说

12、忽略就能忽略？淡定，请接着继续看延伸的例子：算法效率的度量方法i, j, x=0, sum=0, n=100; for( i=1; i = n; i+ )for( j=1; j 2时，算法A1就开始优于算法B1了，随着n的继续增加，算法A1比算法B1逐步拉大差距。所以总体上算法A1比算法B1优秀。规模算法A1（2n+3）算法A2（2n）算法B1（3n+1）算法B2（3n）n=15243n=27476n=396109n=1023203130n=100203200301300函数的渐近增长函数的渐近增长函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的nN，f(n)

13、总是比g(n)大，那么，。从刚才的对比中说f(n)的增长渐近快于g(n)还发现，随着n的增大，后面的+3和+1其实是不影响最终的算法变化曲线的。例如算法A2，B2，在图中他们压根儿被覆盖了。所以，后边可以忽略这些加法常数。给大家举多几个例子，会更明显。函数的渐近增长第二个测试，算法C是4n+8，算法D是2n2+1。再来看一下线性图。次数算法C1（4n+8）算法C2（n）算法D1（2n2+1）算法D2（n2）n=112131n=216294n=3203199n=104810201100n=1004081002000110000n=10004008100020000011000000函数的渐近增长

14、函数的渐近增长观察发现，哪怕去掉与n相乘的常数，两者的结果还是没有改变，算法C2的次数随着n的增长，还是远小于算法D2。也就是说，与最高次项相乘的常数并不重要，也可以忽略。函数的渐近增长再来看第三个测试，算法E是2n2+3n+1，算法F是2n3+3n+1。再来看一下线性图。次数算法E1（2n2+3n+1）算法E2（n2）算法F1（2n3+3n+ 1）算法F2（n3）n=16161n=2154238n=32896427n=1023110020311000n=100203011000020003011000000函数的渐近增长函数的渐近增长这次又发现什么呢？最高次项的指数大的，函数随着n的增长，结

15、果也会变得增长特别快。嗯，进行最后一个小测试，把这些概念都总结起来吧！算法G是2n2，算法H是3n+1，算法I是2n+3n+1。函数的渐近增长次数算法G（2n2）算法H（3n+1）算法I（2n2+3n+1）n=1246n=28715n=5501666n=1020031231n=100200030120301n=100020000003001200301n=1000020000000030001200030001n=1000002000000000030000120000300001n=1000000200000000000030000012000003000001函数的渐近增长函数的渐近增长看

16、出啥？一条直线？当他们数据很小的时候是这样的：函数的渐近增长看得很清楚，当n的值变得非常大这组数据的时候，3n+1已经没法和2n2的结果相比较，最终几乎可以忽略不计。而算法G在跟算法I基本已经重合了。于是可以得到这样一个结论，判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高项）的阶数。注意，判断一个算法好不好，只通过少量的数据是不能做出准确判断的，很容易以偏概全。算法时间复杂度算法时间复杂度的定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作

17、：T(n)= O(f(n)。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。好罗嗦。（关键需要知道执行次数=时间）算法时间复杂度这样用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。一般情况下，随着输入规模n的增大，T(n)增长最慢的算法为最优算法。显然，由此算法时间复杂度的定义可知，的三个求和算法的时间复杂度分别为O(1)，O(n)，O(n2)。三个求和算法？哪有？忘了？好吧，看看以下这张图能不能勾起点回忆？算法时间复杂度推导大O阶方法那么如何分析一个算法的时间复杂度呢？即如何推导

18、大O阶呢？给大家整理了以下攻略：用常数1取代运行时间中的所有加法常数。在修改后的运行次数函数中，只保留最高阶项。如果最高阶项存在且不是1，则去除与这个项相乘的常数。得到的最后结果就是大O阶。世界上的东西就是这么简单，老头儿们把它讲复杂，那么它就复杂了，举几个例子：常数阶sum = 0, n = 100;pr pr pr pr prprf(“f(“f(“f(“f(“f(“o, worldn”);o, worldn”);o, worldn”);o, worldn”);o, worldn”);o, worldn”);sum = (1+n)*n/2;大家觉得这段代码的大O是多少？常数阶O(8)？这是初

19、学者常常犯的错误，总认为有多少条语句就有多少。的概念“T(n)是关于问题规模n分析下，按照的函数”来说，这里跟问题规模有关系吗？没有，跟问题规模的表亲戚都没关系！所以O(1)就可以。记作另外，如果按照攻略来，那就更简单了，攻略第一条就说明了所有加法常数给他个O(1)即可。线性阶一般含有非嵌套循环涉及线性阶，线性阶就是随着问题规模n的扩大，对应计算次数呈直线增长。i , n = 100, sum = 0; for( i=0; i n; i+ )sum = sum + i;上面这段代码，它的循环的时间复杂度为O(n)，因为循环体中的代码需要执行n次。平方阶刚才是单个循环结构，那么嵌套呢？i, j,

20、 n = 100; for( i=0; i n; i+ )for( j=0; j n; j+ )prf(“o, worldn”);平方阶n等于100，也就是说外层循环每执行一次，内层循环就执行100次，那总共程序想要从这两个循环出来，需要执行100*100次，也就是n的平方。所以这段代码的时间复杂度为O(n2)。那如果有三个这样的嵌套循环呢？没错，那就是n3啦。所以很容易总结得出，循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。刚刚每个循环的次数都是一样的，如果：平方阶i, j, n = 100; for( i=0; i n; i+ )for( j=i; j n; j+ )prf(“o

21、, worldn”);惨了，老办法好像在这里套不上了，咋整？！平方阶分析下，由于当i=0时，内循环执行了n次，当i=1时，内循环则执行n-1次当i=n-1时，内循环执行1次，所以总的执行次数应该是：n+(n-1)+(n-2)+1 = n(n+1)/2大家还记得这个公式吧？嗯嗯，没错啦，就是高斯先生发明的算法丫。那咱理解后可以继续，n(n+1)/2 = n2/2+n/2推导大O的攻略，第一条忽略，因为没有常数用相加。第二条只保留最高项，所以n/2这项去掉。第三条，去除与最高项相乘的常数，最终得O(n2)。对数阶对数，属于高中数学内容啦。看下这个程序：i = 1, n = 100;while( i

22、 n )i = i * 2;由于每次i*2之后，就距离n更近一步，假设有x个2相乘后大于或等于n，则会退出循环。于是由2x = n得到x = log(2)n，所以这个循环的时间复杂度为O(logn)。函数调用的时间复杂度分析如果把问题再实际化一点，大家是否能自己正确的分析出来呢？来看下边这个例子：i, j;for(i=0; i n; i+) function(i);void function(count) prf(“%d”, count);函数调用的时间复杂度分析函数体是打印这个参数，这很好理解。function函数的时间复杂度是O(1)，所以整体的时间复杂度就是循环的次数O(n)。假如fun

23、ction是下面这样，又该如何呢：void function(j;count) for(j=count; j n; j+) prf(“%d”, j);函数调用的时间复杂度分析事实上，这和之前讲解平方阶的时候举的第二个例子一样：function的循环次数随count的增加(接近n)而减少，所以根据算法的时间复杂度为O(n2)。攻略接着使出锏，给大家一个的机会！尝试自己分析以下程序的时间复杂度：函数调用的时间复杂度分析n+;function(n); for(i=0; i n; i+) function(i);for(i=0; i n; i+) for(j=i; j n; j+) prf(“%d”,

24、 j);常见的时间复杂度例子时间复杂度术语5201314O(1)常数阶3n+4O(n)线性阶3n2+4n+5O(n2)平方阶3log(2)n+4O(logn)对数阶2n+3nlog(2)n+14O(nlogn)nlogn阶n3+2n2+4n+6O(n3)立方阶2nO(2n)指数阶有图有有图有常见的时间复杂度常用的时间复杂度所耗费的时间从小到大依次是：O(1) O(logn) O(n) O(nlogn) O(n2) O(n3) O(2n) O(n!) O(nn)O(1),O(logn),O(n),O(n2)举例谈过了，至于O(nlogn)介绍。前边已经给大家会在今后的课而像O(n3)之后的这些，

25、由于n值的增大都会使得结果大得难以想象，没必要去它们。算法分析框架输入规模的度量算法效率：一个以算法输入规模n为参数的函数运行时间的度量基本操作（ basic operation ）增长次数算法的最优、和平均效率Cavg(n) Cbest(n)Cworst(n)渐近符号渐进符号 Big-oh、 Big-theta、Big-omegaO(g(n): class of functions f(n) (g(n): class of functions f(n)(g(n): class of functions f(n)t grow no fastern g(n)t grow at same rate

26、 as g(n)t groweast as fast as g(n)基本的渐进效率类型1constant常量log nlogarithmic对数nlinear线性n log nn-log-n or linearithmic线性对数n2quadratic平方n3cubic立方2nexponential指数n!factorial阶乘主要内容绪论算法算法问题求解基础重要类型基本数据结构算法效率分析基础分析框架渐近符号和基本效率类型非递归算法的数学分析 递归算法的数学分析非递归算法的数学分析决定用哪个（或哪些）参数作为算法问题规模的度量找出算法中的基本语句检查基本语句的执行次数是否只依赖于问题规模；如

27、否，三种效率需分别研究建立基本语句执行次数的求和表达式用渐进符号表示这个求和表达式关键：建立一算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。抢答1：um element抢答2： Element uniqueness problem抢答3： Counting binary digits主要内容绪论算法算法问题求解基础重要类型基本数据结构算法效率分析基础分析框架渐近符号和基本效率类型非递归算法的数学分析 递归算法的数学分析递归概念的引入一个小故事：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：山上有座庙，庙里有个老和尚， 老和尚在讲故事，它讲的故事是：小故事的特点？故事中

28、包含了故事本身自己调用自己。例如把上面的讲故事的过程包装成一个函数，就会得到：经典故事的程序设计函数的功能？输出这个故事的内容，等用户按任意键后，重复的输出这段内容。发现由于每个故事都是相同的，所以出现导致死循环的迂回逻辑，故事将不停的讲下去。出现死循环的程序是一个不健全的程序，在满足某种条件以后能够停下来，正如 同的故事后会大叫：“够了！”。希望程序听了几遍相于是可以得到下面的程序：void Story()puts(从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：);getchar();/按任意键听下一个故事的内容Story(); /老和尚讲的故事，实际上就是上面那个故

29、事#includeconstMAX = 3;void Story(n);/讲故事改良的程序main(void)Story(0); getchar();return 0;void Story(if (n 0时什么时候使用递归阶乘的另外一种定义方法当n=0时1n！=n*(n-1) ！当n0时第一种递归这时候递归的定义可以用如下的函数表示：1f(n)=n*f(n-1)也就是说，函数f(n)的定义用到了自己本身f(n1)当n=0时当n0时什么时候使用递归2. 数据结构是递归的有些数据结构是递归的。例如，单链表就是一种递归数据结构,其结点类型定义如下：typedef struct LNode第二种递归E

30、lemType data; struct LNode *next;LinkList;该定义中,结构体LNode的定义中用到了它自身,即指针域next是一种指向自身类型的指针,所以它是一种递归数据结构。什么时候使用递归3. 问题的求解方法是递归的一个典型的例子是在有序数组中查找一个数据元素是否存在的折半查找算法有序数组元素为1;3;4;5;17;18;31;33;寻找值为17的数据第三种递归斐波那契数列在700多年前，意大利有一位著名数学家斐波那契在他的算盘全集一书中提出了这样一道有趣的兔子繁殖问题。如果有一对小兔，每一个月都生下一对小兔，而所生下的每一对小兔在出生后的第三个月也都生下一对小兔。那么，由一对兔子开始，满一年时一共可以繁殖成多少对兔子？用列举的方法可以很快找出本题的：第一个月，这对兔子生了一对小兔，于是这个月共有2对（1+1=2）兔子。第二个月，第一对兔子又生了一对兔子。因此共有3对（1+2=3）兔子。第三个月，第一对兔子又生了一对小兔而在第一个月出生的小兔也生下了一对小兔。所以，这个月共有5对（2+3=5）兔子。第四个月，第一对兔子以及第一、二两个月生下的兔子也都各生下了一对小兔。因此，这个月连原先的5对兔子共有8对（3+5=8）兔子。列表如下：就是说，由一对兔子开始，