第1章
用算法的眼光去看问题
算法真的是非常重要！算法的选择会对软件的性能产生巨大影响。本书将指导你学习一系列的算法，例如搜索和排序，还会介绍一些算法经常采用的策略，例如分治或贪心。希望从此之后，你能够灵活运用这些算法来改善软件的性能。
自“计算”出现之后，数据结构便一直与算法紧密相关。本书将介绍一些基本的数据结构，并展示如何使用这些数据结构来高效地处理数据。
“在选择算法时，你需要做什么？”我们将在接下来的章节中探究这个问题的答案。
1.1 理解问题
设计算法的第一步就是理解将要解决的问题。以一个计算几何领域的简单问题为例：给定一个二维点集P（见图1-1），想象着用一个橡皮圈把这些点围起来，松开之后，这个橡皮圈的形状就是凸包（能够把点集P所有的点全部包围起来的最小凸形）。那么，现在的任务就是编写一个算法，针对一个给定的二维点集，计算它的凸包。
仔细观察点集P的凸包就会发现，连接P中任何两点的线段都位于这个凸包内。假设，我们把凸包中的点按顺时针排好，不难发现，这个凸包其实是由h个顺时针排列的点L0, L1, ..., Lh-1组成，如图1-2所示。每三个相邻的点Li, Li+1, Li+2组成一个向右拐的线条。
有了这样的信息，也许你可以手工画出任意点集的凸包，但是否能写出一个算法呢（给出一系列循序渐进的指令，并且能够高效地计算出任意点集的凸包）？
有趣之处在于，这个凸包问题貌似并不属于任何众所周知的算法范畴。而且，似乎也并没有任何线性时间的排序算法能够按照从左到右顺时针对点进行排序。与此类似，要找到凸包上的一条线段并不难，因为这条线段一定会使得平面上剩余的n-2个点都位于其“右侧”，但也没有显而易见的搜索算法可用。
图1-1：平面上由15个点组成的示例点集
图1-2：图1-1中点的凸包
