算法及其性能分析数据结构与算法

《算法及其性能分析数据结构与算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Slide.2-1教学目的和内容：§了解分析和评价算法的一些基本准则§掌握算法时间复杂性分析方法HIT哈尔滨工业大学计算机科学与技术学院张岩CSTSlide.2-2一、算法、算法的特征和算法描述算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。算法的特征：①有穷性、②确定性、③能行性、④输入、⑤输出常用的算法设计方法：①递归法（Recursion）、②分治法(Divide-andConquer)、③贪心法(Greedy)、④动态规划(D

2、ynamicProgramming)、⑤搜索与遍历、⑥回溯（Backtracking）、⑦解空间局部搜索⑧近似算法(Approximation)、⑨在线算法（On-Line）等HIT哈尔滨工业大学计算机科学与技术学院张岩CSTSlide.2-3二、“好”的算法的标准1.正确性(Correctness)l正确性的含义：是指对于一切合法的输入数据经有限时间或有限步后均可得到正确（满足规格说明要求）的结果；l算法包括两方面的内容：①解决问题的方法；②实现这一方法的一系列指令(语句、步骤)l算法的正确性证明：①需要

3、一组相关的引理和定理，确认一个算法所使用的方法和公式的正确性；②在证明一系列的语句确实做了符合规定的动作。l算法的正确性的严格的形式化证明还未取得突破，还是一项令人生畏的工作。只有那些比较简单的算法，其正确性才能被形式化证明。HIT哈尔滨工业大学计算机科学与技术学院张岩CSTSlide.2-4二、“好”的算法的标准2.时间复杂性(TimeComplexity)l如何计算和比较算法的执行时间：⑴实验测量法（实际执行时间、执行指令的条数）优点：精确缺点：必须先运行根据算法编制的的程序；所得的时间统计量依赖于计算

4、机的硬件、软件等环境因素，容易掩盖算法本身的优劣。HIT哈尔滨工业大学计算机科学与技术学院张岩CSTSlide.2-5二、“好”的算法的标准⑵事前分析(估计)法高级语言编写的程序在计算机上运行时间取决于下列因素：①依据的算法本身选择何种策略②问题的规模（输入的规模，输入的大小）。如求素数问题③程序设计语言：算法的实现语言级别越高，执行效率越低④编译程序产生的机器代码的质量⑤及其执行指令的速度③④⑤表明用绝对的时间单位衡量一个算法的效率是不适合的l算法的时间复杂性①认为一个特定的算法执行时间(“运行工作量”的

5、大小)，只依赖于问题的规模，即算法执行时间是问题规模的函数---T(n)HIT哈尔滨工业大学计算机科学与技术学院张岩CSTSlide.2-6二、“好”的算法的标准②由于算法的执行时间是组成算法的控制结构（顺序、分支和循环）和基本操作的综合效果，因此从算法中选择对于研究问题来说是基本的操作（基本运算）,把算法的基本操作的重复执行的次数作为算法的时间度量③通常，我们并不关心T(n)的具体值，而是关心它的增长率,即T(n)随问题规模n（是一个整数）的增大的变化趋势（界限）④算法的复杂性定义算法中基本操作重复执行的

6、次数是问题规模n的某个函数f（n），算法的时间度量记作T（n）=O（f（n））。它表示随问题规模n的增大，算法执行时间的增长率不会超过f（n），称为算法的渐近时间复杂性，简称时间复杂性。HIT哈尔滨工业大学计算机科学与技术学院张岩CSTSlide.2-7二、“好”的算法的标准3.空间复杂性(SpaceComplexity)l算法的空间复杂性是指算法在执行过程中的存储量需求l一个算法的存储量需求除了存放算法本身所有的指令、常数、变量和输入数据外，还包括对数据进行操作的工作单元和存储实现计算所需信息的辅助空间l

7、算法的存储量需求与输入的规模、表示方式、算法采用的数据结构、算法的设计以及输入数据的性质有关l算法的执行的不同时刻，其空间需求可能是不同的l算法的空间复杂性是指算法在执行过程中的最大存储量需求l空间复杂性的渐近表示----空间复杂度T（n）=O（f（n））其中，n为问题的输入规模HIT哈尔滨工业大学计算机科学与技术学院张岩CSTSlide.2-8二、“好”的算法的标准4.可读性(Readability)l可读性好的算法有助于设计者和和他人阅读、理解、修改和重用l晦涩难懂的算法容易隐藏错误,而且还增加了阅读算

8、法的难度l可读性好的算法，常常也具有简单性5.健壮性(Robustness)l当输入数据非法时，能作出适当的反应（如对输入数据进行语法检查，提出修改输入建议并提供重新输入的机会），避免异常出错6.一个好的算法还应该具有灵活性（Flexibility）、可重用性(Reuseabale)和自适应性(Adaptability)等HIT哈尔滨工业大学计算机科学与技术学院张岩CSTSlide.2-9一、算法的时间复杂性定义