好算法标准

① 正确性： 算法应满足具体问题的需求。

② 可读性： 算法应容易供人阅读和交流。可读性好的算法有助于对算法的

理解和修改。

③ 健壮性： 算法应具有容错处理。当输入非法或错误数据时，算法应能

适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。

④ 通用性： 算法应具有一般性 ，即算法的处理结果对于一般的数据集合

都成立。

⑤ 效率与存储量需求： 效率指的是算法执行的时间；存储量需求指算法

执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。

算法效率的度量

算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。

其方法通常有两种：

事后统计：计算机内部进行执行时间和实际占用空间的统计。

问题：必须先运行依据算法编制的程序；依赖软硬件环境，容易掩盖 算法本身的优劣；没有实际价值。

算法效率的度量

撇开软硬件等有关部门因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用n表示），表示成是问题规模的函数。

算法效率的度量

表示时间复杂度的阶有：

O(1) ：常量时间阶 O (n)：线性时间阶

O(㏒n) ：对数时间阶 O(n㏒n) ：线性对数时间阶

O (nk)： k≥2 ，k次方时间阶

其关系为：

O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)

指数时间的关系为：

O(2 n )<O(n!)<O(n n )

⭐常量阶

{++x; s=0 ;}

将x自增看成是基本操作，则语句频度为１，时间复杂度为Ｏ(1) 。

将s=0也看成是基本操作，则语句频度为２，时间复杂度仍为Ｏ(1)。

⭐ 线性阶

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

++x;

s+=x ;

}

语句频度为：2n，其时间复杂度为：O(n) ，即为线性阶。

⭐ 平方阶

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

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

++x;

s+=x ;

}

}

语句频度为：2n2 ，其时间复杂度为：O(n2) ，即为平方阶。

⭐ 三次方阶

两个n阶方阵的乘法

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] ;

}

由于是一个三重循环，每个循环从1到n，则总次数为： n×n×n=n3 时

间复杂度为T(n)=O(n3)

小结：

空间复杂度的度量

空间复杂度(Space complexity) ：是指算法编写成程序后， 在计算机中运行时所需存储空间大小的度量。记作： S(n)=O(f(n)) 其中： n为问题的规模(或大小)

空间复杂度的度量

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

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

{ ++x; s+=x ; }

临时变量为：i , j ，s，x；空间复杂度为：O(1) ，即常量阶。

复习考研数据结构第二天！！！