计算机数据结构的知识点(12)

健壮性（Rubustness）

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

4．高效率与低存储量需求

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

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

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

1．事后统计法

缺点：

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

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

2.事前分析估算法

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

1．算法选用的策略

2．问题的规模

3．编写程序的语言

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

5．计算机执行指令的速度

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

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

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

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

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

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

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

我们先介绍一个概念：

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

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

语句重复执行的次数被称为语句的频度（Frequency Count）上程序段中++x的语句频度就是n2。

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

例如：

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

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

c[i,j] = 0;

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

c[i,j] += a[i,k]*b[k,j];

}

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

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

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

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

算法的存储量包括:

1．输入数据所占空间;

2．程序本身所占空间；

3．辅助变量所占空间。

若输入数据所占空间只取决与问题本身，和算法无关，