理工大学指挥自动化学院.docx

编写陈卫卫（2008.2）审批理工大学指挥自动化学院课 程 教 案教员姓名： 陈 卫 卫 单 位： 软件技术教研室 课程名称： 算法与数据结构 总 学 时： 60+20 适用对象：生长干部非合训本科学员授课学期： 2008年春季学期 理工大学训练部制表课程简介一、课程定位算法与数据结构是仿真工程（非合训）、网络工程（合训）、作战信息管理（非合训）专业的本科生学科专业基础课程中的一门重要的核心课程。通过本课程的教学，使学员知道数据结构的一般原理，掌握表、树、图等基本数据结构的特点、存储表示、具有的运算、实现运算的算法设计方法，以及对算法效率的评估方法，知道什么是好的算法，如何设计和选择好的算法，为学习后续的操作系统、编译原理、软件工程等专业课程，设计系统程序打下基础。本课程的先修课程为：计算机程序设计导论（C语言）、离散数学。二、课程内涵（一）总体目标通过本课程的教学，使学员懂得数据结构的一般原理，掌握表、树、图等基本结构的特点，各结构的存储表示和所具有的运算，实现各运算的算法，学会对算法的评估方法。培养学员的算法设计能力、程序设计能力以及用软件方法处理问题的能力，培养学员的分析、对比、归纳、综合和创新能力，为学习后续专业课程，设计系统程序打下坚实的理论基础。（二）主要内容本课程主要内容包括两大部分。一是基本概念，主要介绍算法和数据结构的概念，算法的描述方法和评价标准、评价方法；算法设计的一般方法。这部分教学的主要目的是使学员了解算法和数据结构的一般原理，了解对算法的评估方法。二是最基本的数据结构表结构、树结构和图结构，通过对表、树、图等基本结构的特点、存储方法，查找、插入、删除、排序、图的最优化等算法，以及实现运算的算法设计方法的学习，培养学员的算法设计能力、程序设计能力以及用软件方法处理问题的能力。（三）对学员的要求能够熟练地使用C语言。三、教学设计算法和数据结构是一门理论性与实践性都很强的重要核心课程。课程实施的总体方案是以提高学员的应用能力、创新能力和综合素质为目标，总体上，按照先易后难，先简单后复杂的思路进行讲解。在每一堂课上，大体的讲课思路是：先分析问题的特点，抽象出数据以及数据之间的关系，然后，引导学员寻找解决问题的思路和方法，最后考虑如何编程实现，让学生体验解决问题的一般过程。对于基本概念，多举例阐述概念的内涵，强调术语的作用，规范用词，培养严谨的科学作风。对于算法设计，突出重点，以点带面，通过对比，使学员逐步建立设计“好”算法的意识。具体内容如下：1围绕表、树、图三大基本结构选择授课内容，依照“逻辑结构物理结构基本运算基本算法算法评价”这个脉络，研究每种结构的特点，给学生一个清晰的研究过程，使学员能够根据问题的特点选择合适的数据结构，进一步理解研究数据结构的意义。2教学方法采用引导、启发、研究、讨论、问题驱动等多种形式，充分发挥学员的主体作用，激发每个学员的特长和潜能，培养学员的想象力和创新能力。3教学手段采用多媒体和板书相结合的形式，全方位、多角度地阐述教学内容。利用多媒体动画，揭示算法思想的内涵，使算法思想更为形象、直观，提高学生的学习兴趣和求知欲。4以知识验证、知识综合、创新设计为原则，设计上机实验内容。实验分为两类，一类为理解知识点的基本实验，另一类为综合应用的实验。通过上机编程强化学生的程序设计能力，进一步消化理解理论授课内容，贯彻“学以致用”的思想。教学进度总体安排序号教 学 内 容课堂教学学 时实践教学学时网络教学学时1概述2学员自主学习2表结构1863树结构1864图结构1045排序826集合运算227算法设计的一般方法2总计6020教学进度具体安排第一章 概述 4学时第1讲 算法和数据结构概述2学时第30讲 算法设计的一般方法2学时第二章 表结构 18学时第2讲 表结构的概念2学时第3讲 顺序表的运算2学时第4讲 链表的基本概念2学时第5讲 简单链表的运算2学时第6讲 复杂链表及链表的应用2学时第7讲 栈和队2学时第8讲 静态链表2学时第9讲 矩阵运算2学时第10讲 字符串2学时第三章 树结构 18学时第11讲 树结构的概念2学时第12讲 二叉树2学时第13讲 二叉树的遍历2学时第14讲 遍历算法的应用2学时第15讲 遍历序列的性质2学时第16讲 二叉树的构造2学时第17讲 检索树2学时第18讲 平衡树2学时第19讲 哈夫曼树、判定树2学时第四章 图结构 10学时第20讲 图的概念和存储结构2学时第21讲 先深搜索和先广搜索2学时第22讲 最小生成树2学时第23讲 最短路径2学时第24讲 有向无回路图、双连通分量2学时第五章 排序8学时第25讲 基本概念、插入排序2学时第26讲 交换排序2学时第27讲 选择排序2学时第28讲 合并排序、基数排序2学时第六章 集合运算2学时第29讲 散列表2学时说明：为了空出一次复习课的时间，在实施计划中将第11讲和第12讲压缩为了一次课。内 容备 注第一章 概 述第1讲 算法和数据结构概述讲课题目：算法和数据结构概述（1.1、1.2、1.3）目的要求：1了解课程基本信息，建立基本要求2掌握基本数据结的构特征及其意义3掌握算法的定义和三种描述方式4了解算法的评价方法知识点：1数据结构的基本概念2算法的描述和实现3算法的评价方法重点难点：1表、树、图结构的特征及其意义2算法的定义，算法的描述方式3算法的时间复杂性方法步骤： 1介绍与课程有关的相关知识2从求解问题的一般步骤入手，建立抽象的数据模型（数值、非数值）3用示例抽象说明数据，以及数据之间的关系，介绍数据结构的分类和特征4用示例介绍算法的描述形式和适用场合，研究算法“好”、“坏”问题的意义和价值，站在使用效果、满足需要等角度，讨论研究评价算法的标准。器材保障：电脑、投影仪、教鞭教学内容与时间安排:板书一、课程基本信息 10 分钟（一）教员信息主讲教员：陈卫卫联系方式： 824546(O) ，828596(H)E_mail： hchcww办公室：教学楼809 介绍课程整体情况，帮助学生明确学习目标，知道相关的学习要素。（二）课程的主要任务使学员获得算法和数据结构方面的基本知识，培养学员的程序设计能力和初级算法设计能力，掌握运用计算机解决本专业实际问题的基本方法，为今后的工作和学习奠定坚实的基础。（三）教学重点和基本条件1教学重点在于围绕算法指导学生编程，使学生知道什么是“好”的算法，如何才能学会编写高质量的程序。2基本条件：熟练使用C语言（C+中的传引用功能）、有一定的离散数学知识掌握VC+6.0集成开发环境（四）教材及参考书目1教材 (Text Book)数据结构教程 王庆瑞编著 北京希望电子出版社2参考书 一般的学会搜集资料，知道参考书的作用和价值，以及如何使用参考书。充实、深化相关学习内容。Data Structures and Algorithm Analysis in C（Second Edition）， Mark Allen Weiss 著，陈越改编，北京：人民邮电出版社，2005 数据结构（C语言版） 严蔚敏、吴伟民 编著 清华大学出版社C算法（第一卷，基础、数据结构、排序和搜索）（第三版）Algorithms IN C(THIRD EDITION)C算法（第二卷 图算法） Robert Sedgewick著 周良忠 译，人民邮电出版社 POSTS & TELECOM PRESS 经典的 计算机程序设计艺术（第3版）The Art of Computer Programming第1卷 基本算法第2卷 半数值算法第3卷 排序与查找Donald E.Knuth 著 苏运霖 译，国防工业出版社 Addison Wesley，2003结合课程特点，强调好的学习方法。（五）学习方法l 认真听讲l 读书、思考l 独立完成作业l 上机练习（六）评价方式l 平时作业（含上机）l 上课表现l 笔试试卷板书二、数据结构的概念 20 分钟板书（一）问题的求解过程总结归纳问题求解的一般过程，从中把握数据结构课程的地位和作用。说明：算法和程序概念的差异，在没有歧义的情况下，可以不区别。1解题的一般过程l 接受任务（设计程序、软件）l 针对问题进行分析l 设计出求解策略，即算法（algorithm），程序的雏形“问题级的算法”（或初级算法）l 算法的需要，抽象出所要处理的数据l 建立数据结构l 将算法分解成对数据结构的运算l 设计出对数据结构进行处理的算法（数据结构级算法）l 对算法的性能（可行性和运行效率：时间和空间）进行评估l 着手程序设计l 对程序进行调试l 交付使用2程序与算法的关系程序是按算法思想进行设计的，程序中含有算法。算法就是程序（但算法不等于程序）。程序也称算法。程序（或算法）就是问题的解（算法解，或程序解，软件解）。板书（二）数据和数据结构从狭义和广义两个角度阐述数据。举例说明这些术语的内涵，进一步理解计算机的工作方式。板书1数据是对客观事物的名称、数量、特征、性质的描述形式（编码），是计算机所能处理的一切符号的总称，是程序加工的对象和产品。板书2数据的种类数值型数据（整数、实数等）：例，四则运算文字型数据（字符、字符串）：例，文本文件，程序代码（编译软件）声音、图像形式的数据：例，mp3、avi。数据总是以某种编码形式出现的。板书3数据结构研究的对象数据元素的集合，元素之间的关系，对数据和数据集合进行哪些运算，如何提高运算效率。板书4数据元素（data element）说明：为了简化问题，后面仅讨论单数值结点。但是原理相同。数据结点，简称结点（node）。描述一个独立事物的名称、数量、特征、性质的一组相关信息组成一个数据结点。通常，一个结点含有多个数据项（记录型结点，或结构型结点）每个数据项是结点的一个域（field），能够唯一标识结点的域叫关键字域（key）。若结点只含一个数据项（单值结点），可把结点看成整数（编码）。例如：（1）学生结点：学生的姓名、学号、各科考试成绩等等，学号可以作为结点的关键字域。（2）商品结点：商品编号和名称、规格、数量、生产厂家、单价、入库日期。板书5数据结构（data structure）强调：5要素：1数据2关系3运算4算法5评价数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和处理算法的学科。（1）定义：数据结构B=(D，R) 逻辑结构D：有穷的结点集合；R：D中结点间的有穷关系集合注意：不研究一个结点内部各域之间的关系（由编码，存储方式决定）。板书（2）研究内容补充：在面向对象环境下，有人将程序的概念进行了拓展。数据及数据之间的关系、存储方式、基本运算、实现运算的算法、算法评价方法。数据结构程序编写算法设计问题求解l “好”数据结构“好”算法“好”程序l 良好、合理的数据结构l 清晰、实用的算法l 简洁、高效的程序板书（3）数据结构的两个方面1）数据的逻辑结构：指各数据元素之间的逻辑关系，是用户按使用需要建立起来的，呈现在用户面前的结构形式。2）数据的物理结构：亦称数据的物理结构、存储结构，是指数据在计算机内的表示方法，即存储形式。既要存储数据，又要（存储）体现出逻辑结构。主要概念有：l 存储结点：用于存储一个数据结点的存储单元。一个数据结点对应一个存储结点（统称结点）。l 空白结点：预留的存储结点（尚未存储数据的存储结点）。亦称空结点、自由结点。板书举例说明，这些逻辑关系。学会从一般到具体，把握概念的内涵。6常见的逻辑数据结构板书表、树、图、集合（1）表：描述结点之间简单的先后次序关系。一对一关系（2）树：描述结点之间的层次关系，或嵌套关系。一对多关系（3）图：描述结点之间的“多对多”关系。（4）集合：结点之间的“无关关系”。结构中的数据元素之间除“同属于一个集合”的关系，无其他关系。板书7基本存储结构从存储角度看，数据结构可以归结为两种基本结构：板书（1）顺序存储结构把逻辑上相邻的结点存储在物理位置上相邻存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。板书（2）链接存储结构 不要求逻辑上相邻的结点其物理位置上亦相邻，结点间的逻辑关系是由附加的指针域表示的。板书8运算（operation）：对数据和数据结构的处理操作。不同的数据结构有不同的运算。如表结构的常见运算：查找、插入、删除、排序等。阐述运算的特征，以及关联关系，将特殊的运算一般化（分裂、合并等等）。（1）插入(Insert) 在数据结构的指定位置上增添新的数据元素。 （2）删除(Delete) 删去数据结构中某个指定的数据元素。（3）更新(Update) 改变数据结构中某个数据元素的值，在概念上等价于删除和插入操作的组合。（4）查找(Search) 在数据结构中寻找满足某个特定要求的数据元素(位置或值)。 板书三、算法的描述和实现 30 分钟板书（一）算法(Algorithm)的定义1简单定义：算法记载了求解问题的方法和步骤。举例说明算法的5个重要特性的内涵。提问：与计算方法的区别？算法(Algorithm)是对特定问题求解步骤的一种描述，是能在计算机上经过有限时间完成的、毫不含糊的指令的有限序列。其中每一条指令表示一个或多个操作。2克努特（D.E.Knuth）的定义：算法就是一个有穷规则的集合。规则规定解决某一特定问题的运算序列。算法的5个重要特性。有穷性、确定性、输入、输出、可行性（算法中所有的运算都可以精确地实现）。（1）有穷性：执行有限步，每步均在有穷时间内完成。（2）确定性：对相同的输入，必产生相同的输出，即无二义性。（3）可行性：计算机可使用已实现的基本运算执行有限次来完成。（4）输入：零个或多个输入。（5）输出：一个或多个输出。板书（二）算法的存在形式1程序形式程序形式算法的实现算法的最终形式。学会交流算法的各种方式。知道什么场合选用什么样的描述方式。2描述形式描述形式：便于理解、记忆和互相交流三种描述形式： 形式化、半形式化、非形式化。3形式化描述用类语言描述的形式“半程序”形式。伪程序（伪代码）。类语言：以某种程序设计语言（C语言）作为“宿主语言”略加改造而形成的语言。语法不那么严格，可以使用“杂牌语句”，省略类型定义、变量定义、输入/输出等细节，保留程序的基本框架。伪程序与“真程序”非常接近，略加改造就是真程序。4半形式化流程图。常用的流程图符号（一种语言）。5非形式化文字叙述形式，最原始形式。6示例例1.1 自然选择排序算法。把一组（共n个）杂乱数据排列成由小到大的递增序列。最简单的一种方法是简单选择法（simple selection sort），或自然选择法。（1）文字叙述形式：举例说明三种描述方法的特点。讨论：非形式化和半形式化的缺点？改进的方法？通过讨论明晰三者之间的关系。先从n个数据中选出一个最小元素，使它作为序列的第一项；再从剩下的n-1个数据中选出一个最小元素作为第二项，重复地作上述选择工作，直至选择最后一项。最终将得到有序序列。算法不依赖数据结构，不考虑数据是如何存储的。（2）进一步叙述：假定数据存储在数组an中：先从a的n个元素中选择一个最小元素（比如某个aj），将它与a0交换位置；再从剩下的n-1个元素中选择一个最小元素，将它与a1交换位置；再从剩下的n-2个元素中选择一个最小元素，将它与a2交换位置；反复进行上述选择和交换，直到选择出最后一个元素，从而完成排序工作。（3）用类C程序（形式化）：for(i=0;i<n-1;i+) k=i; for(j=i+1;j<n;j+) if(aj<ak) k=j; w=ai; ai=ak; ak=w; 例1.2 二分查找（binary search）算法。在元素从小到大排列的有序数组an中，查找一个元素x（变量），如果x在数组a中出现，就用变量i记住它所在的数组下标，若x不出现，则i= -1。二分查找算法：（1）文字叙述步骤1置left和right的初值，即left=0，right=n-1；步骤2如果left>right，则查找不成功（即数组a中没有x），使i= -1，算法终止；否则：步骤3计算中值地址，即下标mid=(left+right)/2；步骤4比较x与amid的值： （4.1）如果x=amid，则找到x，i=mid，算法终止；否则， （4.2）如果x<amid，则调整右指针right，使right=mid-1，转到步骤2继续查找； （4.3）如果x>amid，则调整左指针left，使left=mid+1，转到步骤2继续查找。这样，反复执行步骤（2）到（4），就能完成查找工作。（2）流程图：P5 图1.3 二分查找算法的流程图板书7三种算法描述形式小结（1）自然语言叙述：简单易懂，适合于对算法的设计思想进行讲解；有二义性。（2）流图：直观、结构更清晰，容易理解，接近程序形式；也有二义性，比较麻烦，不容易修改。常用于对大型软件的结构分析和说明。（3）伪代码形式：克服二义性，突出算法的主体，保持算法的良好结构，可采用逐步求精的程序设计方法。便于对算法时间、空间作定量的分析。板书8算法和程序的关系程序（Program）是用计算机程序设计语言实现的完成一定功能的代码。算法的程序形式称为算法的实现（例如，C语言程序等），是算法的最终形式。提问：计算组合的算法设计思想？一起讨论学生的算法的优劣，引出算法评价标准问题。程序中体现了算法的思想。算法不依赖于具体的实现语言。程序中有算法，算法不一定是程序。板书四、算法的评价标准 5 分钟（一）算法分析对算法的综合性能进行较为客观的分析评价评估，评测（二）评价角度（标准）板书1算法的正确性(Correctness)能满足具体问题的需求，且所有合法的输入数据都正确才算正确。评价方法：l 调试精心挑选具有“代表性”的，“刁钻性”的数据进行调试。只能证明算法有错，不能证明算法无错。l 人工证明（归纳法）板书2算法的有效性（算法的运行效率）强调研究有效性的重要意义。算法的运行效率(Efficiency)耗用时间，占用空间。（1）算法的时间复杂性（time complexity）：对时间的客观要求。同一问题，算法执行时间越短，效率越高。（2）算法的空间复杂性（space complexity）：对空间的客观要求。指算法执行过程中所需的最大存储空间。3对程序（软件）评价的附加标准（1）操作界面（2）健壮性(Robustness)从算法和程序评价上的差异辨识二者的差别。对于异常的处理能力。能作出判断，并给出适当的提示或警告信息，以等待操作员的干预或能自动进行适当处理。（3）可读性(Readability)希望一个算法易于理解、易于编码，也易于调试。（4）可维护性等等。板书五、算法的时间复杂性 20 分钟板书分析计算法时间复杂性的困难之处，剖析可能的计算方法，寻找可行的解决办法，既可以学到基本知识，也在学习的过程中贯穿对方法论和认识论的学习。（一）算法的时间复杂性函数1T(n)n是输入数据量的大小（问题的一个参数）。描述算法执行过程中所需的时间用量与问题规模n之间的函数关系T(n)。T(n)要计算得“精确”（客观）很因难。2计算的困难性执行时间取决于下列因素：l 问题的规模（输入的大小/复杂程度）l 所选用的语言l 编译程序所产生可执行代码的质量l 机器执行指令的速度（二）可能的方法1事后统计 对程序的执行时间进行计时。（有缺陷，有局限性）思考：用具体的时分秒度量可以吗？2事前估计事先估算的主要因素问题的规模。例6： 两个n×n矩阵相乘，令数乘作为基本运算for( i = 1; i <= n; i+ ) for( j = 1; j <= n; j+ ) Cij = 0; for( k = 1; k <= n; k+ ) Cij += Aik * Bkj;整个算法执行时间与数乘次数n3成正比，记作T(n)=O(n3) 两个n×n矩阵相乘的时间复杂度为O(n3)。板书明确度量单位的意义，学会把握“标准”。（三）时间度量单位时间单位：每执行一条基本语句耗用一个时间单位（比较粗些）。T(n)等于执行基本语句的总条（次）数。大体上能够说明算法的时间性能。板书（四）大“O”记号1T(n)的上界补充：的含义。（1）定义对某算法执行时间T(n)，如果存在正的常数c和n0，使对于一切n > n0，T(n)cf(n)都成立。即T(n)cf(n) （c是任意正的常数常系数，f(n)是具体的函数。）那么，就记作T(n)=O(f(n)反之，如果一个程序的时间复杂度是O(f(n)，就说该程序的运行时间增加率的一个上界为f(n)，或说T(n)是f(n)的大O函数。 （2）内涵只求出T(n)随输入数据量n而增长的趋势（极限情况）算法的渐近时间复杂性（asymptotic time complexity），而且不追求“精确”形式，只求出T(n)的“阶”。只求出T(n)的最高阶，忽略其低阶项和常系数。（3）示例设T(n)=n2+4n，则有f(n)=n2，即有：n2 + 4n = O(n2)因为存在c=2，n0=4，使对于一切n>n0，恒有n2 +4n2 n22优点（1）简化T(n)的计算（2）比较客观地反映出当n很大时，算法的时间性能。3示例对某问题，设计了两个算法，经过计算得出：算法A的时间耗费函数为T1(n)=20n2+100n算法B的时间耗费函数为T2(n)=0.5n23n+18这两个算法的时间耗费函数的阶是一样的，都是n的平方阶的，于是可以写成T1(n)=O(n2)T2(n)=O(n2)记忆时间耗费函数的常用阶的大小关系，帮助分析问题，寻求更好的解，或者选用更好的算法。当n很大时，低阶算法比高阶算法好。板书4常用阶O(1)常数时间，即算法时间用量与输入数据量n的大小无关O(logn)对数时间，对数阶通常不写底数（底数无关）因为任何常数C1，C2>0，有O(logc2n)=O(logc1c2 logc1n)=O(logc1n) 因为logc1c2是常数O(n)线性时间，即算法时间用量与n成正比O(n logn) 非常理想的阶O(n2) 平方阶O(n3)立方阶强调有效算法和无效算法的划分方式，理解“有限”时间的内涵。大致学会判断算法的有效性。以上都是多项式阶。凡T(n)= O(nd)时（d是任意一个正的常数），都属于“有效算法”。O(2n)指数阶O(n!)阶乘阶则是无效算法，当n稍大一点，就不能在“有限的”时间内完成。示例：某算法的时间复杂性T(n)=2n，当n=1000时，其工作量（执行基本语句条数）将达到21000，假定每执行一条基本语句需要花费1毫微秒（10-9秒）时间，那么解此问题共需要：板书（五）最坏情况和平均情况1为什么要区分两种情况若某算法，对不同的输入数据（输入数据量都是n）耗用时间的差别很大，为使评价更客观，更有说服力，所以需要分几种情况讨论算法的时间性能。最坏情况（worst-case）和平均情况（expected-case），即算法的最坏性态和平均性态。举例说明区分最坏情况和平均情况的重要意义。学会全面思考问题的方法。从这两个角度分析算法的时间性能，可以给算法作出更为客观的评价。2最坏情况对于具有相同输入数据量的不同输入数据，算法时间用量的最大值。用TW(n)表示最坏情况。3平均情况对于所有相同输入数据量的各种不同数据，算法耗用时间的平均值。有时还要考虑各种不同输入数据出现的可能性（即概率）。用TE(n)表示平均情况下算法时间复杂性。4注意（1）一般不讨论“最好”情况下算法的时间复杂性。（2）如果某算法最坏情况和一般情况时间用量相差不多，就没有必要区分两种不同情况了。笼统地用T(n)表示算法时间。板书三、算法的空间复杂性 5 分钟研究空间复杂性的作用，建立时空转换意识，学会灵活处理问题的方法。1算法空间用量函数S(n)算法执行时所需空间（即占用内存单元数目）。通常只计算辅助空间用量，而不计原始数据所占的空间。2示例自然选择排序算法。for(i=0;i<n-1;i+) k=i; for(j=i+1;j<n;j+) if(aj<ak) k=j; w=ai; ai=ak; ak=w; 原始数据占用空间：n辅助空间（“纯”空间）：4（i，j，w，k）S(n)=O(1)由简单到复杂，了解一般的计算方法。培养分析问题的意识。板书3时空转换有时，为了节省时间，先进行某种“预处理”，记下一些信息（多用辅助数组）。板书四、计算时间复杂性的一般方法 10 分钟板书（一）典型语句度量法1执行次数最多的语句（起支配性作用的典型语句）。“最多”是指：其他语句花费时间的总和将不超过这个语句花费时间的常数倍。用典型语句的执行次数度量这段程序花费时间的阶。若这段程序形如，语句1；语句2；语句s；语句m;假定语句s共执行f(n)次，除语句s外，其他语句执行次数总和不超过cf(n)次（c是常数，即与n无关），于是，这段程序共执行f(n)+cf(n)=(c+1)f(n)根据渐近复杂性的定义，这段程序的时间耗费是O(f(n)。注意：这样的语句可能不止一条。注意：语句序号（1，2，3）不是程序的一部分，而是语句标号，便于陈述说明。2示例示意性程序：for(i=1,c=0,s=a0;i<n;i+) 1. if(ai<a0) /统计小于a0的元素个数2. c+=1;3. s+=ai; /计算数组元素的总和 可选句1（元素比较次数）作为支配性语句，由于它共执行n-1次（或O(n)次），所以这段程序耗费时间是O(n)。3典型语句的选择方法（1）一般情况，可以任选。但是要符合“最多”要求。（2）比较为主的算法中（如排序、查找一类的算法）通常以比较次数度量算法的时间复杂性。其中，查找算法常常以“查找长度”（与多少个元素比较过）度量时间用量。（3）以算术运算（包括加减乘除和赋值）为主的算法，用算术运算次数度量算法的时间用量。在算法理论上，分为“算法类”。板书（二）分段计算法分段相加法（加后化简）。注意，只取高阶项。若一段耗时为O(f(n)，另一段耗时为O(g(m)，那么两段共耗费O(f(n)+O(g(m)=O(f(n)+g(m)例如，O(n2)+O(n)=O(n2)O(n)+O(n)=O(n)板书（三）分层计算法分层相乘，再化简1简单相乘多重循环（或函数嵌套调用），分别计算各层的执行次数，再相乘。若外层循环共执行O(f(n)次，外层每执行一次内层循环都要执行O(g(m)次，那么两层共执行O(f(n)O(g(m)=O(f(n)g(m)次。示例：示意性程序：for(i=0;i<n;i+)1. x=y=0; for(j=0;j<n/2;j+)2. if(aj>ai) x+=1;3. if(aj<ai) y+=1; priintf("%d,%dn",x,y); 外循环共执行n次，外循环每执行一次，内循环都执行n/2次，注意到O(n/2)=O(n)，所以本段程序时间复杂性为O(n)*O(n)=O(n2)注意：分层相乘有时不够精确，过于“粗糙”。可能会算多了。2直接计算内循环总的执行次数例如，for(i=1;i<=n;i+) for(j=1;j<=i;j+) printf("%d",i*j);显然，外循环第i次执行时，内循环执行i次，所以内循环总的执行次数等于板书（四）递推式方法利用组合论知识，列出关于时间耗费函数的递归方程（或递归不等式），通过求解递归方程，计算出时间复杂性。示例：焚塔问题的时间耗费。用T(n)表示搬动高度为n的塔所需的移动总次数，那么可得出下列递归方程：板书（五）其他方法利用“便于”计算的数学模型，和复杂的数学演算（包括微分和积分运算），计算T(n)。板书（六）算法的选用原则总原则：能用就行（能满足客观要求）。需要考虑如下因素。l 算法实现的难易程度。l 算法使用的次数，和是用于否实时处理（如通信、天气预报等）。l 算法运行环境（输入数据量的大小范围）当数据量不大时，低阶算法未必就快。例如，算法A1和A2的时间复杂性分别为T1(n)=1000n和T2(n)=n2虽然O(T1(n)<O(T2(n)，但是只有当n>1000时，A1才好于A2；而当n1000时，A2却好于A1，因为T2(n)T1(n)。小结：1数据、数据结构、研究对象、逻辑结构、物理结构2常见的4种基本数据结构及特点3基本运算4算法的描述方式5算法的评价标准（正确性、有效性）6时间复杂性（大O记号、有效算法、无效算法）、空间复杂性作业：P25 1.1、1.2（选）思考题：1列举一些你知道的数值类问题的数学模型。参考资料：1 Mark Allen Weiss 著，陈越改编，Data Structures and Algorithm Analysis in C（Second Edition），北京：人民邮电出版社，20052严蔚敏编著，数据结构，北京：清华大学出版社，20033王晓东编著，算法设计与分析，北京：清华大学出版社，2003本次课教学体会：第30讲 算法设计的一般方法（简介）讲课题目：算法设计的一般方法目的要求：1了解有效算法设计方法2了解递归方法、分治方法、动态规划法、贪心法、搜索-回溯法、平衡原则。知识点：递归、分治法、贪心法、动态规划、平衡原则、回溯重点难点：各种算法设计方法的特点、可以解决的问题方法步骤： 1举例介绍问题，总结归纳方法器材保障：电脑、投影仪、教鞭教学内容与时间安排:板书归纳总结前人的智慧，拓展学习能力，培养创新能力。一、算法设计的一般方法 5 分钟算法“无法”靠人们的智慧和灵感，针对不同问题设计不同算法。常用方法归类：递归法、分治法、动态规划法、贪心法、搜索-回溯法、平衡原则。板书二、递归（recursion） 30 分钟（一）好处结构简