算法技术手册（原书第2 版）

算法的数学原理

｜

23

算法的

数学原理

在复杂性理论中，还有一种

Θ

(

f

(

n

))

表示，它融合了上下界的思想，用于描述精确的

紧

界

（

tight bound

），即下界为

Ω

(

f

(

n

))

时，上界则是使用相同分类函数

f

(

n

)

的

O

(

f

(

n

))

。

我们采用更为广泛接受的（更加非正式一些的）

O

(

f

(

n

))

来简化算法表示和分析。我们保证，

在讨论算法性能时，如果一个算法被认定为

O

(

f

(

n

)),

一定不会存在更为精确的

f'

(

n

)

可以

对算法进行分类。

2.4 性能指标

在比较算法时，我们使用了问题数据的规模

n

来评估算法的性能。这是过去半个世纪算

法比较的标准方法。通过输入数据的规模评估算法的执行时间，我们可以知晓哪种算法

能够更好地适应一些异常规模的问题。性能评估的第二种方法是考虑算法将会耗费多少

内存或者存储空间。之后的小节详细讨论这个问题。

常见的算法分类（按照效率降序排列）如下：

•

常数级：

O

(

1

)

•

对数级：

O

(log

n

)

•

次线性级：

O

(

n

d

)

，其中

d

< 1

•

线性级：

O

(

n

)

•

线性对数级：

O

(

n

log

n

)

•

平方级

:

O

(

n

2

)

•

指数级：

O

(

2

n

)

注意：在评估算法性能时，必须要找到算法中计算费用最大的部分才能决定算法的分类。

例如，如果一个算法可以被划分为两个任务，其中一个任务为线性级，另一个任务为平

方级，那么这个算法的总体性能应当归为平方级。

下面将通过一些例子来阐释这些不同的性能分类。

2.4.1 常数级算法的性能

在分析算法性能时，本书常常会强调原生操作都具有常数级的性能。很明显，这个声明

并不能完全准确地描述实际操作的性能，因为它没有考虑到硬件问题 ...