《数据结构》--算法.

第2章算法计科系：王丹丹复习1、什么是数据结构？2、本课程主要研究什么？3、什么是数据的逻辑结构和物理结构？4、数据的逻辑结构有哪几种？存储结构有哪两种形式？5、逻辑结构与物理结构间的关系？数据结构主要研究什么？数据结构是一门研究数据的各种逻辑结构和存储结构，以及对数据各种操作的课程。数据的逻辑结构数据的存储结构数据的操作(算法)：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构本章内容2.2数据结构与算法关系2.3两种算法的比较2.4算法定义2.5算法的特性2.6算法设计的要求2.7算法效率的度量2.8函数的渐近增长2.9算法时间复杂度2.10常见的时间复杂度2.11最坏情况和平均情况2.12算法空间复杂度2.1.3总结回顾要能回答的问题1、算法与程序的区别？2、算法的评价标准？3、什么是算法的时间复杂度？4、怎样计算算法的时间复杂度？•思考：写一个求1+2+3+……+100结果的程序？2.4算法的定义算法(Algorithm)：对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。程序:计算机能够理解和执行的指令序列。算法与程序的区别和联系算法的执行是有穷的，而一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。2.5算法的特性输入输出一个算法应该有零个或多个输入，一个或多个输出。有穷性一个算法必须在执行有穷步之后结束。确定性算法中的每一步必须有确切的含义，无二义性。可行性算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。2.6算法设计的要求评价一个好算法的几个标准正确性(Correctness)：算法应满足具体问题的需求。可读性(Readability)：算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。健壮性(Robustness)：算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。算法的设计与分析算法的设计1、通过对问题进行详细地分析，抽象出相应的数学模型；2、确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；3、描述算法（C语言中的函数）；4、选用某种语言将算法转换成程序；5、调试并运行这些程序。算法的设计与分析算法的设计算法能用文字、高级语言、伪代码进行描述。案例按学号进行顺序查找NO=20020005的学生。设i=1，比较第i个元素的学号是否等于NO,如果相等，则查找成功，查找过程结束；否则，i++，继续比较。学生信息表中，所有元素的学号都不等于NO，则查找失败。算法设计的要求正确性1可读性健壮性时间效率高和存储量低234时间效率：算法的执行时间。如何度量？•思考：算法的优劣？事后统计方法：利用计算机计时器对不同算法编制的程序的运行时间进行比较。事前分析估计方法：计算机程序编制前，依据统计方法对算法进行估算。2.7算法效率的度量方法缺陷事后统计方法花费大量的时间和精力依赖计算机硬件和软件等环境因素算法的测试数据设计困难事先分析估算方法-运行消耗时间算法采用的策略、方法01编译产生的代码质量02机器执行指令的速度04问题的输入规模03因素算法好坏软件支持输入量的多少硬件性能第一种算法第二种算法执行：1+（n+1）+n+1=2n+3次执行：1+1+1=3次例子延伸算法的执行次数：对于同样输入规模，要多于前面两个。算法的执行时间：随着n的增加也将远远多于前两种。测定运行时间最可靠的方法：计算对运行时间有消耗的基本操作的执行次数。运行时间与这个计数成正比！启示•同样问题，输入规模为n求和算法操作数量第一种F(n)=n第二种F(n)=1第三种F(n)=n*n不同算法的操作数量对比随着n值的越来越大，它们在时间效率上的差异也就越来越大。2.8函数的渐近增长观察数据的特点？判断：算法A和B哪个更好？函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的nN，f(n)总是比g(n)大，那么，我们说f(n)的增长渐近快于g(n)。可以忽略这些加法常数！2.8函数的渐近增长与最高次项相乘的常数并不重要！2.8函数的渐近增长最高次项的指数大的，函数随着n的增长，结果也会变得增长特别快。2.8函数的渐近增长判断一个算法好坏，我们只通过少量的数据是不能做出准确判断的。对比算法的关键执行次数函数的渐近增长性，基本可以分析：某个算法，随着n的增长，它会越来越优于另一种算法，或者差于另一算法。这其实是事前估算方法的理论依据，通过算法时间复杂度来估算算法时间效率。2.9算法时间复杂度算法中基本操作重复执行的次数是问题规模n的某个函数，其时间度量记作：T(n)=O(f(n))，称作算法的渐近时间复杂度(AsymptoticTimecomplexity)，简称时间复杂度。一般常用最深层循环内的语句中的原操作的执行频度（重复执行的次数）来表示。大O符号：用于描述函数渐近行为的数学符号。它是用另一个函数来描述一个函数数量级的渐近上界。其中f(n)是问题规模n的某个参数。2.9.2推到大O阶方法用常数1取代运行时间中的所有加法常数。在修改后的运行次数函数中，只保留最高阶项。如果最高阶项存在且不是1，则去除这个项相乘的常数。得到的结果就是大O阶。2.9.3常数阶时间复杂度是多少？2.9.3常数阶时间复杂度是多少？2.9.3常数阶事实上无论n为多少，上面的两段代码就是3次和12次执行的差异。这种与问题的大小无关（n的多少），执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又叫常数阶。注意：不管这个常数是多少，都记作O(1)；单纯的分支结构，其时间复杂度也是O(1)。2.9.4线性阶线性阶的循环结构会复杂很多。要确定某个算法的阶次，我们常常要确定某个特定语句某个语句集的运行次数。因此，我们要分析算法的时复杂度，关键就是要分析循环结构的运行情况。时间复杂度是多少？2.9.5对数阶时间复杂度是多少？2.9.6平方阶时间复杂度是多少？2.9.6平方阶时间复杂度是多少？循环时间复杂度等于循环体的复杂度乘以该循环运行的次数。2.9.6平方阶时间复杂度是多少？2.9.6平方阶时间复杂度是多少？2.9.6平方阶时间复杂度是多少？2.9.6平方阶时间复杂度是多少？2.10常见的时间复杂度执行次数函数阶非正式术语12O(1)常数阶2n+3O(n)线性阶平方阶对数阶立方阶指数阶常用的时间复杂度所耗费的时间从小到大依次是：O(1)O(㏒n)O(n)O(n㏒n)O(n2)O(n3)O(2n)O(n!)O(nn)2.11最坏情况与平均情况最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。一般在没有特殊说明的情况下，都是指最坏时间复杂度。2.12算法空间复杂度算法的空间复杂度通过计算算法所需的存储空间实现。算法空间复杂度的计算公式记作：S(n)=O(f(n))。其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。例1：{++x;}将++x看成是基本操作，则语句频度为1，其时间复杂度为O(1)，即常数阶。例2：for(inti=1;i=1000;i++){++x;}将++x看成是基本操作，则语句频度为1000，其时间复杂度仍为O(1)，即常数阶。例3：for(i=1;i=n;++i){++x;}语句频度为n，其时间复杂度为：O(n)例４：for(i=1;i=n;++i)for(j=1;j=n;++j){++x;}语句频度为n2，其时间复杂度为：O(n2)定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)例５：for(i=2;i=n;++i)for(j=2;j=i-1;++j){++x;}语句频度为1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=(n2-3n+2)/2∴时间复杂度为O(n2)，表示为：T(n)=O(n2)第二章习题1.1下面程序的时间复杂度为_____。for(i=1，im；i++)for(j=0；jn；j++)A[i][j]=I＊j;A.O(m2)B.O(n2)C.O(m＊n)D.O(m+n)1.2下列程序的时间复杂度为X=n;/*n1*/y=0;while((x=(y+1)*(y+1))y=y+1;A.O(n)B.O()C.O(1)D.O(n2)n1.3下列程序的时间复杂度为inti=1;while(i=n)i=i*2;A.O(n2)B.O(log2n)C.O()D.O(n)答案：CBBn复习1.算法与程序的区别？2.算法的特性及其评价标准？3.什么是算法的时间复杂度？4.怎样计算算法的时间复杂度？Tobecontinued…