数据结构复习重点归纳（适于清华严版教材)[4]

算法和算法分析

Algorithms and Algorithm Analysis

算法

所谓算法(Algorithm)是对问题求解步骤的一种描述是指令的有限序列其中每一条指令表示一个或多个操作在CLRS中是这样给出算法的定义的Informally an algorithm is any welldefined computational procedure that takes some value or set of values as input and produces some value or set of values as output An algorithm is thus a sequence of computational steps that transform the input into the output

一个算法必须满足以下五个重要特性

有穷性 对于任意一组合法输入值在执行有穷步骤之后一定能结束即算法中的每个步骤都能在有限时间内完成;

确定性 对于每种情况下所应执行的操作在算法中都有确切的规定使算法的执行者或阅读者都能明确其含义及如何执行并且在任何条件下算法都只有一条执行路径;

可行性 算法中描述的操作都可以通过已经实现的基本操作运算有限次实现之;

有输入 作为算法加工对象的量值通常体现为算法中的一组变量有些输入量需要在算法执行过程中输入而有的算法表面上可以没有输入实际上已被嵌入算法之中;

有输出 它是一组与输入有确定关系的量值是算法进行信息加工后得到的结果

算法设计的原则

设计算法时我们应当严格考虑

正确性(Correctness)

首先算法应当满足以特定的规格说明方式给出的需求对算法是否正确的理解可以有以下四个层次

a程序中不含语法错误;

b程序对于几组输入数据能够得出满足要求的输出结果;

c程序对于精心选择的典型苛刻的几组输入数据能够得出满足要求的结果;

d程序对于一切合法的输入数据都能得出满足要求的结果;

通常以第c层意义的正确性作为衡量一个算法是否合格的标准因为作为输入我们有时候不可能提前做出所有的预期

可读性(Readability)

算法主要是为了人的阅读与交流其次才是为计算机执行因此算法应该易于人的理解;另一方面晦涩难读的程序易于隐藏较多错误而难以调试;有些程序设计者总是把自己设计的算法写的只有自己才能看懂这样的算法反而没有太大的价值

健壮性(Rubustness)

当输入的数据非法时算法应当恰当地作出反映或进行相应处理而不是产生莫名奇妙的输出结果这就需要我们一定要充分的考虑异常情况(Unexpected Exceptions)并且处理出错的方法不应是中断程序的执行而应是返回一个表示错误或错误性质的值以便在更高的抽象层次上进行处理

高效率与低存储量需求

通常效率指的是算法执行时间;存储量指的是算法执行过程中所需的最大存储空间两者都与问题的规模有关

算法效率的衡量方法与准则

通常有两种衡量算法效率的方法:

事后统计法

缺点

()必须执行程序才能进行判断

()其它因素(如硬件软件环境)掩盖算法本质

事前分析估算法

主要是看消耗的时间和算法执行时间相关的因素

算法选用的策略

问题的规模

编写程序的语言

编译程序产生的机器代码的质量

计算机执行指令的速度

一个特定算法的运行工作量的大小只依赖于问题的规模(通常用整数量n表示)或者说它是问题规模的函数假如随着问题规模n的增长算法执行时间的增长率和f(n)的增长率相同则可记作

T (n) = O(f(n))

称T (n) 为算法的渐近时间复杂度(Asymptotic Time Complexity)简称时间复杂度O是数量级的符号

下面我们探讨一下如何估算算法的时间复杂度

算法 = 控制结构 + 原操作(固有数据类型的操作)

算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间

算法的执行时间与原操作执行次数之和成正比

我们先介绍一个概念

for(j=;j <=n;++j)

for(k=;k <=n;++k){++x;x+=x;}

语句重复执行的次数被称为语句的频度(Frequency Count)上程序段中++x的语句频度就是n

我们经常采用从算法中选取一种对于所研究的问题来说是基本操作的原操作以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则这个原操作多数情况下是最深层次循环内的语句中的原操作

例如

for (i=; i <=n; ++i)

for (j=; j <=n; ++j) {

c[ij] = ;

for (k=; k <=n; ++k)

c[ij] += a[ik]*b[kj];

}

该算法的基本操作是乘法操作时间复杂度为 O(n)

算法的存储空间(Memory Space for Algorithms)

算法的空间复杂度S(n) = O(g(n))

表示随着问题规模n的增大算法运行所需存储量的增长率与g(n)的增长率相同

算法的存储量包括:

输入数据所占空间;

程序本身所占空间;

辅助变量所占空间

若输入数据所占空间只取决与问题本身和算法无关则只需要分析除输入和程序之外的额外空间若所需额外空间相对于输入数据量来说是常数则称此算法为原地工作

[] [] [] []