下载掌阅APP，畅读海量书库
立即打开
算法这个词最早出现在波斯数学家阿勒·花刺子密（Al-Khwarizmi）在公元825年所写的《印度数字算术》中。那么，什么是算法？简单来说，算法就是针对特定问题的解决思路、方法和步骤。算法在计算机中表现为表示一个或多个操作的指令有限序列，一种算法就是将输入转换为输出的一系列计算步骤。
算法必须满足有穷性、确定性、可行性、存在输入及存在输出等5个重要特性。
有穷性指算法在执行有限的步骤之后会自动结束，并且每一个步骤都在可接受的时间内完成。例如，C语言的一条语句 while(true){ }，该语句中循环条件为真，将一直执行循环体{ }。然而该循环体为空语句，如果没有break语句，语句将一直执行下去，这种情况称为死循环，在一般程序中是不允许出现的。但是，有穷性是个相对的概念，有时出现在网络服务器代码中是允许的，因为服务器通常需要处于连续工作当中。
确定性指算法的每一步必须有确切的定义，无二义性。算法在每种情况下的操作都有明确的规则，这避免了因操作的歧义性而使得计算机程序无法执行。
算法的每一步操作都是可行的，都能够通过基本运算执行有限次数完成。可行性意味着算法可以转换为计算机程序并得到正确的结果。不过，存在一些极其复杂的算法，理论上是可以实现的，但实际上受编程方法、工具等条件限制却不能实现。
算法具有零个或多个取自特定数据对象集合的输入。有些算法看起来没有输入，但实际上已经有处理好的数据嵌入算法中或者已经存在于计算机中。
一个算法具有零个或多个输出，这些输出与输入之间存在某种确定关系。输出是执行算法后，对数据进行加工处理得到的结果，这个结果可以是数据，也可以是操作过程执行结束后得到的对错/是否等信息。
算法与数据结构是相辅相成的。算法可以选择不同的数据结构，选择是否恰当直接影响算法效率的高低；数据结构的优劣由算法的执行来体现。
在算法设计中，针对同一个问题可以设计出多个不同的算法来解决它。如何评价这些算法并从中选择最优算法呢？
算法设计的要求通常包括以下5个方面。
（1）正确性。算法的正确性是指算法的输入/输出和加工处理无歧义，能够正确反映问题的需求，并且得到问题的正确答案。
算法的“正确性”大体分为4个层次：算法程序没有语法错误；合法的输入能够产生满足要求的结果；非法的输入数据能够得出满足规格说明的结果；对于特殊的输入数据也都有满足要求的结果。证明一个复杂算法在这4个层次上都是正确的，代价非常高。一般情况下，仅把第3层次作为一个算法是否“正确”的评判标准。
（2）可读性。算法的变量命名、格式符合行业规范，并在关键处给出注释，以提升算法的可理解性。
（3）稳健性。算法对于异常输入数据，或者出现错误操作后，能够给予错误提示信息，保证程序正常运行或者终止程序。
（4）时间高效性。时间效率指的是算法的执行时间，对于同一个问题可以有多个算法，执行时间短的算法效率高，执行时间长的效率低。这也就是算法的时间复杂度。
（5）低存储量。存储量通常包括算法在运行时所使用的变量、数据结构以及系统调用栈等所占用的内存空间。解决同一问题额外占用的临时存储空间越少，算法的空间效率就越高。算法存储量通常用空间复杂度来度量。
事后统计法和事前分析估算法是衡量算法效率的两种方法。事后统计法需要先将算法实现，然后测算其时间和空间开销。这就要求：①必须把算法转换成可执行的程序；②测算结果依赖于计算机软硬件等环境因素，而这样做容易掩盖算法本身的优劣。因此，通常采用事前分析估算法，借助计算算法的渐进复杂度来衡量算法的效率。
同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，执行的时间都可能不相同。一个算法的执行时间大致上等于它所有语句执行时间的总和，而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积。由于语句的执行时间受编译器、硬件环境等因素影响，所以计算语句的真实执行时间是不可取的。这时尝试可采用算法中语句的执行次数之和
来度量该算法的执行时间，即
T
(
n
)=
f
(
n
)。
【例1-1】 求两个 n 阶矩阵相加的算法。
for (i=0; i<n; i++) // 语句频度为n+1
for (j=0; j<n; j++) // 语句频度为n*(n+1)
c[i][j]=a[i][j]+b[i][j]; // 语句频度为n*n
该算法所有语句的频度之和
，是问题规模
n
的函数，且随着
n
的增大而增大。然而，对于上述较简单的算法，
是相对比较复杂的。这给不同算法间时间效率的比较带来不便。从
的表达式可以看到，随着
n
的增加，
的大小主要是由最高阶项决定，它正好对应了基本运算（加法或赋值）的执行次数；同时
中的最高阶也反映算法时间对问题规模的变化趋势（快慢）。所以，一般情况下并不用实际执行时间来衡量算法的效率，而是关注算法的时间开销对于问题规模变化的趋势。
设问题的规模为
，即算法输入量的大小，算法的执行时间可用其基本操作的执行次数来度量。所谓的“基本操作”是指算法中执行次数最多的元操作，如加法、减法、乘法、除法、赋值、移位和逻辑运算等。为了进一步简单地反映算法时间的变化趋势，引入了渐进时间复杂性的理论。从数学意义上讲，算法时间的变化趋势集中体现
的阶。
对于
T
(
N
)，如果存在
(
N
)，使得当
N
→∞时有：
称
(
N
)是
T
(
N
)当
N
→∞时的渐进复杂性。显然
(
N
)不是唯一的。我们可以尽可能选择简单的
(
N
)，然后使用
(
N
)来替代
T
(
N
)作为
N
→∞的复杂性度量。例如：
T
(
n
)=3
n
2
+4
n
log
n
+7;
(
n
) =3
n
2
T
(
n
)=4
n
log
n
+7
n
;
(
n
) =4
n
log
n
进一步地，基于“
O
”给出渐进时间复杂性的定义。若
T
(
n
)和
f
(
n
)是定义在正整数集上的两个函数，则
T
(
n
)=
O
(
f
(
n
))表示存在正的常数
c
和
n
0
，使得当
n
≥
n
0
时都有0≤
T
(
n
)≤c
f
(
n
)。该定义说明
T
(
n
)的增长量阶不高于
f
(
n
)的增长量阶，而大多数情况下取与
f
(
n
)相同的增长量阶。
表示随问题规模
的增大，算法执行时间的增长量阶，称为算法的渐进时间复杂度，简称为时间复杂度。
【例1-2】 常量阶示例。
{a=a+i, i++;}
上面语句中，加法、赋值和自加操作均执行一次，相应的执行时间是一个与问题规模 n 无关的常数。因此，该算法的时间复杂度 T ( n )= O (1)，称为常量阶。
【例1-3】 线性阶示例
temp=0;
for(i=0; i<n; i++)
temp+=a[i];
上面的算法中，赋值和加法是基本操作，均执行 n 次。因此，该算法的时间复杂度 T ( n )= O ( n )，称为线性阶。
【例1-4】 平均阶示例。
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if (a[i]>a[j]) {
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
上面算法中，
a
[
i
]>
a
[
j
]是基本操作，执行次数为：
，则该算法的时间复杂度为
T
(
n
)=
O
(
n
2
)，称为平方阶。
对某些具体问题，相应算法的基本操作不仅仅与问题的规模有关，也依赖于其他因素，如下例所示。
【例1-5】 在一维数组 a 中查找某个值等于 e 的元素，若存在则返回其所在位置。
for (i=0; i<n; i++) if (a[i]==e) return i+1; return 0;
容易发现，“a[i]==e”的执行次数不仅与问题规模 n 有关，而且与数组 a 中各元素的值及分布和元素 e 的值有关。假定数组 a 中存在等于 e 的值，则查找必定成功，同时“ a [ i ]== e ”的执行次数随着被查找到元素位置的不同而不同。最好的情况是 a [1]等于 e ，此时仅需执行一次，即 f ( n )=1；最坏的情况是 a [ n −1]等于 e ，此时需执行 n 次。然而，对于一个算法来讲，需要考虑所有可能出现的情况，以及每种情况出现的概率。通常情况下，被查找元素在数组各个位置上出现的概率均相同（1/ n ），此时取查找到每个位置上“ a [ i ]== e ”执行次数的平均值，容易算出执行次数的平均值f( n )= n /2。此例说明，算法的时间复杂度不仅问题的规模 n 有关，还可能与问题的其他因素有关，而这些因素影响着算法复杂度的试题。因此，有时人们会对算法有最好、最坏以及平均时间复杂度的评价。
算法在最好情况下的时间复杂度被称为最好时间复杂度，此时的计算量可能达到最小值。算法在最坏情况下的时间复杂度被称为最坏时间复杂度，这时的计算量可能达到最大值。算法的平均时间复杂度是指在考虑所有可能情况下，按照输入实例以等概率出现时算法计算量的加权平均值。
对于算法的时间复杂度，人们可能更关心其平均时间复杂度和最坏时间复杂度。在许多情况下，算法的平均时间复杂度很确定。在此背景下，人们在讨论算法时间复杂度时更多的是最坏时间复杂度，即最坏情况下，算法执行时间的上界。在本书后面讨论的时间复杂度，除非特别说明，均指最坏时间复杂度。
一个算法在计算机存储器上所占的存储空间，包括存储算法本身所占用的存储空间、算法输入/输出数据所占用的存储空间，以及求解问题所需的辅助空间（也可以说是临时存储空间）。空间复杂度指的就是最后那部分临时存储空间，元素本身的大小不在空间复杂度的考虑范围之内。
在实际算法中，时间效率和空间效率往往不可兼得。通常来说，一个算法如果在空间复杂度保持不变的情况下能够提高时间性能，该算法性能就得到了改进。随着硬件设备性能的提高及内存价格的降低，大多数情况下会牺牲空间来换取时间性能的提高。