凸壳算法时间复杂度的归约化分析

5.1　凸壳算法时间复杂度的归约化分析

在算法求解中，归约原理是一种把未知复杂问题转化为另一已知简单（或简明，下同）问题的好方法，就是把一个未知问题归约为另一个已知问题，从而把一个未知复杂问题的计算复杂度，等价地归结为另一个已知简单问题的计算复杂度。

事实上，凸壳算法的时间复杂度分析颇为繁难，故有凸壳算法研究者利用归约原理来把凸壳算法的时间复杂度问题归约为排序（即分类）算法的时间复杂度问题，从而有利于对其进行算法时间复杂度分析。同样，在讨论凸壳算法的时间复杂度问题的下界时，也可以通过归约技术，把两个问题的下界联系起来研究。如果未知复杂问题A能归约成另一个已知简单问题B，就可把研究难度较大的未知复杂问题A的算法复杂度，归结（或转化）为研究难度较小的已知简单问题B的算法复杂度研究。这样，对已知简单问题B的复杂度的求解，要比未知复杂问题A的算法复杂性的求解要容易。

定义5.1　归约方法与步骤，可简要表述为如下“三步曲”：

归约1：把问题A的输入，转化为问题B的相应输入；

归约2：对问题B进行求解；

归约3：把问题B的解输出，转换为问题A的解输出。

定义5.2　设所论问题A、问题B的问题规模均为n，而r（n）为n的多项式。若定义5.1的归约1和归约3，可在O（r（n））时间内完成；则称问题A以多项式时间归约于问题B，记为A∞r（n）B，并称问题A和问题B是r（n）时间等价的。如果r（n）为n的线性函数，则称问题A以线性时间归约于问题B，记为A∞nB，并称问题A和问题B是等价的。

显然，当问题A等价于问题B（即：问题A以线性时间归约于问题B）时，问题A和问题B具有相同的算法复杂度。

图5.1　把凸壳问题归约化为排序问题

1978年，Shamos发现凸壳问题与排序问题之间有密切联系，并根据归约方法，利用其可对凸壳顶点进行排序的性质，由排序问题的下界而变通地得到凸壳问题的下界。

如图5.1所示，假设给定平面点集S={Q_i（x_i，y_i）∣i=1，2，3，…，n}，这些点Q_i（x_i，y_i）总在所求凸壳Q上，同时也都（或近似）在抛物线y=x²上，即必有y_i=x²。显然，耗费n−1次比较i可以找到y坐标最小的点，即耗费O（n）时间可以求得凸壳的一个顶点（即最低顶点）Q₁（x₁，y₁），它对应于Y轴坐标最小者y₁。在凸壳Q上，由顶点Q₁开始按逆时针方向排列的凸壳顶点Q_i的Y轴坐标，实际上可视为“对集合{y_i∣i=1，2，3，…，n }进行排序”的结果。这样，就把凸壳顶点Q_i与Q_i的X轴坐标排序结果联系起来；从而，可转化为利用已知的排序算法复杂度，来等价地认识和描述未知的凸壳算法复杂度。

实际上，设T_A（n）是凸壳算法A构造具有n个顶点的凸壳所需时间复杂度（包括：获取凸壳所在点集S={Q_i（x_i，y_i）∣i=1，2，3，…，n}的子算法需耗费时间O（n），进行排序即寻找凸壳顶点Q_i的子算法所耗费时间），则凸壳算法A的寻找凸壳顶点可归约化为对 “对集合{y_i∣i=1，2，3，…，n }中n个数据进行排序”的排序算法B，且凸壳算法A的时间复杂度T_A（n）可归约化为排序算法B的时间复杂度T_B（n）。

因已知排序算法B求解排序问题所耗费时间复杂度T₂（n），其获取集合{y_i∣i=1，2，3，…，n }中n个数据的子算法需耗费时间复杂度为O（n），而其最坏情况下的时间下界为T₂（n）= O（n log n），故有：

T₁（n）=T₂（n）=O（nlogn）+O（n）=O（nlogn）

据此，可得凸壳算法时间复杂度近似定理：

定理5.1（凸壳算法时间复杂度近似定理）设平面点集S={Q_i（x_i，y_i）∣i=1，2，3，…，n}，一维点集P={y_l，y₂，…，y_n}，各点Q_i（x_i，y_i）总在所求凸壳Q上，且也都（或近似）在抛物线y=x²上，记求S的凸壳算法为Convex_Hull、记使P中各数有序化的排序算法为Data_Sorting；则Convex_Hull的凸壳算法时间复杂度下界可近似归约为Data_ Sorting的凸壳算法时间复杂度下界O（n log n）。

证明：设集合P={y_i∣i=1，2，3，…，n}由点Q_i（x_i，y_i）∈S的Y轴坐标构成，并以此作为使平面点集S的正实数集合P={y_l，y₂，…，y_n}排序问题的一个输入。

首先，因这n个点Q_i（x_i，y_i）必都在抛物线y=x²上（如图5.1所示），故总可把集合P中每一个实数y_i∈P，映射到二维平面上的对应点P_i=（x_i，x_i²），1≤i≤n；从而，可把凸壳问题的输入归约为排序问题的输入。显然，这一归约变换过程只需用线性时间即可完成。

其次，在用求解凸壳问题的任一算法对所论输入数据集求解出其凸壳各顶点后，总可用极点坐标有序表来顺序存放所得凸壳各顶点。

最后，顺序读取该极点坐标有序表中每一点Q_i对应的X坐标值，则得到原实数P集的已有序化的新实数序列y_l，y₂，…，y_n。显然，这一归约化处理过程也只需用线性时间便可完成。故凸壳问题的输入，也可采用线性时问变换为排序问题的输出。

因此，由已知排序算法在最坏情况下的时间下界为O（n log n），而可得知凸壳算法在最坏情况下的时间下界也可近似为O（n log n）。证毕。