数据结构与算法-哈工大 DSA2

《数据结构与算法-哈工大 DSA2》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构与算法第二章算法及其性能度量2—1数据结构与算法第二章算法及其性能度量2—22.1算法及其性能评价准则一、算法、算法的特征和算法描述算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。教学目的和内容：算法的特征：§了解分析和评价算法的一些基本准则①有穷性、②确定性、③能行性、④输入、⑤输出§掌握算法时间复杂性分析方法算法描述：①自然语言；②程序设计语言；③类语言*；2.1算法及其性能评价准则常用的算法设计方法：2.2算法时间复杂性分析方法①递归法（Recursion）、②分治法(Divide-andConquer)

2、、③贪心法(Greedy)、④动态规划(DynamicProgramming)、⑤搜索与遍历、⑥回溯（Backtracking）、⑦解空间局部搜索⑧近似算法(Approximation)、⑨在线算法（On-Line）等哈尔滨工业大学计算机科学与技术学院张岩哈尔滨工业大学计算机科学与技术学院张岩数据结构与算法第二章算法及其性能度量2—3数据结构与算法第二章算法及其性能度量2—42.1算法及其性能评价准则2.1算法及其性能评价准则二、¡°好¡±的算法的标准二、¡°好¡±的算法的标准1.正确性(Correctness)2.时间复杂性(TimeComplexity)l正确性的含义：是指对于一切合法的

3、输入数据经有限时间或有限步后均可得到正确（满足规格说明要求）的结果；l如何计算和比较算法的执行时间：l算法包括两方面的内容：①解决问题的方法；②实现这一方⑴实验测量法（实际执行时间、执行指令的条数）法的一系列指令(语句、步骤)优点：精确l算法的正确性证明：①需要一组相关的引理和定理，确认一缺点：必须先运行根据算法编制的的程序；所得的时间统计个算法所使用的方法和公式的正确性；②在证明一系列的语句量依赖于计算机的硬件、软件等环境因素，容易掩盖算法本身确实做了符合规定的动作。的优劣。l算法的正确性的严格的形式化证明还未取得突破，还是一项令人生畏的工作。只有那些比较简单的算法，其正确性才能被形式化证

4、明。哈尔滨工业大学计算机科学与技术学院张岩哈尔滨工业大学计算机科学与技术学院张岩1数据结构与算法第二章算法及其性能度量2—5数据结构与算法第二章算法及其性能度量2—62.1算法及其性能评价准则2.1算法及其性能评价准则二、¡°好¡±的算法的标准二、¡°好¡±的算法的标准⑵事前分析(估计)法②由于算法的执行时间由组成算法的控制结构（顺序、分支和高级语言编写的程序在计算机上运行时间取决于下列因素：循环）和基本操作的综合效果，因此从算法中选择对于研究问①依据的算法本身选择何种策略题来说是基本的操作（基本运算）,把算法的基本操作的重复执②问题的规模（输入的规模，输入的大小）。如求素数问题行的次数作为

5、算法的时间度量③程序设计语言：算法的实现语言级别越高，执行效率越低③通常，我们并不关心T(n)的具体值，而是关心它的增长率,即④编译程序产生的机器代码的质量T(n)随问题规模n（是一个整数）的增大的变化趋势（界限）⑤及其执行指令的速度④算法的复杂性定义③④⑤表明用绝对的时间单位衡量一个算法的效率是不适合的算法中基本操作重复执行的次数是问题规模n的某个函数l算法的时间复杂性f（n），算法的时间度量记作T（n）=O（f（n））。它表示①认为一个特定的算法执行时间(¡°运行工作量¡±的大小)，只依随问题规模n的增大，算法执行时间的增长率不会超过f（n），赖于问题的规模，即算法执行时间是问题规模的函

6、数称为算法的渐进时间复杂性，简称时间复杂性。哈尔滨工业大学计算机科学与技术学院张岩哈尔滨工业大学计算机科学与技术学院张岩数据结构与算法第二章算法及其性能度量2—7数据结构与算法第二章算法及其性能度量2—82.1算法及其性能评价准则2.1算法及其性能评价准则二、¡°好¡±的算法的标准二、¡°好¡±的算法的标准3.空间复杂性(SpaceComplexity)4.可读性(Readability)l算法的空间复杂性是指算法在执行过程中的存储量需求l可读性好的算法有助于设计者和和他人阅读、理解、修改和l一个算法的存储量需求除了存放算法本身所有的指令、常重用数、变量和输入数据外，还包括对数据进行操作的工

7、作单元和l晦涩难懂的算法不容易隐藏错误，而且还增加了阅读…难度存储实现计算所需信息的辅助空间l可读性好的算法，常常也具有简单性l算法的存储量需求与输入的规模、表示方式、算法采用的数5.健壮性(Robustness)l当输入数据非法时，能作出适当的反应（如对输入数据进行据结构、算法的设计以及输入数据的性质有关语法检查，提出修改输入建议并提供重新输入的机会），避免l算法的执行的不同时刻，其空间需求可能是不同的异常