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

7

第

1

章

用算法的眼光去看问题

算法真的是非常重要！算法的选择会对软件的性能产生巨大影响。本书将指导你学习一

系列的算法，例如搜索和排序，还会介绍一些算法经常采用的策略，例如分治或贪心。

希望从此之后，你能够灵活运用这些算法来改善软件的性能。

自“计算”出现之后，数据结构便一直与算法紧密相关。本书将介绍一些基本的数据结构，

并展示如何使用这些数据结构来高效地处理数据。

“在选择算法时，你需要做什么？”我们将在接下来的章节中探究这个问题的答案。

1.1 理解问题

设计算法的第一步就是理解将要解决的问题。以一个计算几何领域的简单问题为例：给

定一个二维点集

P

（见

图

1-1

），想象着用一个橡皮圈把这些点围起来，松开之后，这个

橡皮圈的形状就是

凸包

（能够把点集

P

所有的点全部包围起来的最小凸形）。那么，现

在的任务就是编写一个算法，针对一个给定的二维点集，计算它的凸包。

仔细观察点集

P

的凸包就会发现，连接

P

中任何两点的线段都位于这个凸包内。假设，

我们把凸包中的点按顺时针排好，不难发现，这个凸包其实是由

h

个顺时针排列的点

L

0

,

L

1

, ...,

L

h

-1

组成，如图

1-2

所示。每三个相邻的点

L

i

,

L

i

+1

,

L

i+

2

组成一个向右拐的线条。

有了这样的信息，也许你可以手工画出任意点集的凸包，但是否能写出一个算法呢（给

出一系列循序渐进的指令，并且能够高效地计算出任意点集的凸包）？

有趣之处在于，这个凸包问题貌似并不属于任何众所周知的算法范畴。而且，似乎也并

没有任何线性时间的排序算法能够按照从左到右顺时针对点进行排序。与此类似，要找 ...