第2讲：算法与算法的分析.ppt

IT Education Training * 数据结构 Neusoft Institute of Information IT Education Training * 姓 名：李德光 系 部：计算机系 办公地址： C7201 E--mail: lideguang@ 第一章：绪论 * 复习： 1、什么是数据结构？ 2、本课程主要研究什么？ 3、什么是数据的逻辑结构和物理结构? 4、数据的逻辑结构有哪几种？存储结构有哪两种形式？ 第一章：绪论 * 要能回答的问题 1.算法与程序的区别？ 2. 算法的评价标准？ 3.什么是算法的时间复杂度？ 4.怎样计算算法的时间复杂度？ 第一章：绪论 * 五、算法 算法： 算法是为解决一个问题而采取的方法和步骤。 程序是计算机能够理解和执行的指令序列。 算法与程序的区别和联系： (1) 算法的执行是有穷的，而一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。 (2)程序中的指令必须是机器可执行的，而算法中的指令则无此限制。 (3）算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序. 第一章：绪论 * 六、算法的设计与分析 算法的设计 1、通过对问题进行详细地分析，抽象出相应的数学模型； 2、确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法； 3、描述算法（C语言中的函数） 4、选用某种语言将算法转换成程序；（C语言） 5、调试并运行这些程序。 第一章：绪论 * 算法的设计 算法能用文字、高级语言、伪代码进行描述 第一章：绪论 六、算法的设计与分析 案例：在学生信息表中,按学号进行顺序查找 NO=200020005的学生 学号 姓名 年龄王红 18张明 19吴宁 18林云 20刘强 18 设i=1，比较第i个元素的学号是否 等于NO,如果相等，则查找成功，查 找过程结束；否则，i++，继续比较。 学生信息表中，所有元素的学号都 不等于NO，则查找失败。 * 算法设计的要求和评价标准 (1) 正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。 (2) 可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。 (3) 健壮性：算法中拥有对输入数据、打开文件、读取文件记录、分配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选择。 (4) 高效性：有效使用存储空间和有较好的时间效率。 第一章：绪论 * 算法的优劣： 问题：求2+4+6+……+2n的值 1.2 算法及算法分析 算法1： int sum = 0,i; for(i=2;i=2*n;i=i+2) {sum = sum+i;} 算法2： int sum = (2+2*n)*n/2; * 算法效率的度量：算法定量的评价 1.事后统计——收集此算法的执行时间和实际占用空间的统计资料。 1.2 算法及算法分析 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———所以使用绝对时间单位衡量算法效率不合适。因此一般常用时间的一个数量级来衡量 缺点：?必须先运行根据算法描述编写的程序 ?所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣 2.事前分析估计 一个高级语言程序在计算机上运行所消耗的时间取决于： ?依据的算法选用何种策略 ?问题的规模 ?程序语言 ?机器执行指令速度 * 时间复杂度-大概程序要执行的次数，而非执行的时间 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)。则时间量度记作： T(n)=O(f(n))，称作算法的时间复杂度。 表示：随问题规模n的增大，执行时间的增长率和f(n)的增长率相同。 通常，时间复杂度只考虑问题规模n的增长率，无需精确，故，只需求出它关于n的增长率或阶即可。 1.2 算法及算法分析 * 计算算法时间复杂度： 1、选取算法中基本操作语句（通常是最内层循环体语句）； 2、计算该语句的频度（频度是指该语句重复执行的次数）； 3、取语句频度