凸壳新算法时间复杂度的案例分析

5.3　凸壳新算法时间复杂度的案例分析

限于篇幅，下面仅以第3章第3.4节所论“单域双向水平倾角最值化圈绕凸壳新算法”为例，给出本书所给出凸壳新算法的时间复杂度之案例分析。

不失一般性，可假定“单域双向水平倾角最值化圈绕凸壳新算法”：

（1）其基本运算：为比较每个点的斜率大小的运算（其中包括了一次计算sin x值的运算和几次进行数值大小比较的步骤）。

（2）其总计点数：设有二维点集S由“凸壳顶点n个，凸壳内点m个”组成，即S的总计点数为m+n个。

一、找到顶点所需要的基本运算次数

（1）对逆时针方向圈绕所求得的凸壳顶点为Q_逆i与顺时针方向圈绕所求得的凸壳顶点为Q_顺i，其圈绕处理的基本运算次数如下：

找到Q_逆0（亦即Q_顺0）：0次；

找到Q_逆1，Q_顺1：1次（计算凸壳边Q_逆1Q_逆0、Q_顺1Q_顺0的斜率）；

找到Q_逆2，Q_顺2：3次（计算凸壳边Q_逆2Q_逆1、Q_顺2Q_顺1的斜率）；

找到Q_逆3，Q_顺3：5次（计算凸壳边Q_逆3Q_逆2、Q_顺3Q_顺2的斜率）；

……

找到Q_逆x，Q_顺x：2x−1次（计算凸壳边Q_逆xQ_逆x−1、Q_顺x Q_顺x−1的斜率）。

（2）对于所论凸壳的n个顶点：

若凸壳顶点个数n为奇数，则所求得的最末一对凸壳顶点Q_{逆（n−1）/2}与Q_{顺（n−1）/2}，必定为彼此独立、互不相同的两个顶点，故其所需基本运算次数为：

若凸壳顶点个数n为偶数，则所求得的最末一对凸壳顶点Q_{逆（n−1）/2}与Q_{顺（n−1）/2}，必定两点重合（即它们实际上是同一个顶点），故其所需基本运算次数为：

二、排除内点所需要的基本运算次数

不失一般性，可假设“单域双向水平倾角最值化圈绕凸壳新算法”：

其内点判定与删除时间复杂度：判定一个内点并将它删除，其时间复杂度为k个基本运算（k可根据具体算法分析算出，k的值大概在0.5～1之间）。

（1）内点不同位置不同，其排除内点的时间复杂度各有不同；故有：

内点在直线Q_逆1Q_顺1下方时，其内点排除基本运算次数为：k+1；

内点在直线Q_逆2Q_顺2下方时，其内点排除基本运算次数为：k+3；

……

内点在直线Q_逆xQ_顺x下方时，其内点排除基本运算次数为：k+（2x−1）。

（2）假设每一个内点，完全随机地出现在各个分布域，即其内点为均匀分布；则此时，判定该点为内点所需运算量的数学期望为：

若凸壳顶点个数n为偶数，判定各点是否为内点所需运算量的数学期望为：

应当说明：当n较大时，k的存在与否对数学期望结果影响不大，故（k+n−2）一式中的k可以去掉（注意：最后两个顶点确定后，所剩余各点已可不必进行其内点判定）。这里，各式中仍有“+k”，仅为便于计算。

若凸壳顶点个数n为偶数，判定各点是否为内点所需运算量的数学期望为：

应当指出：该式中，没有加项“（k+n−1）”，因为最后一个顶点一旦确定后，就已无需再判定内点，故可直接退出凸壳顶点寻找处理。

三、结论

（1）当凸壳顶点个数n为奇数时，该算法的平均时间复杂度为：

n²/2−n+1/2+m[（n−1）/2+k]

（2）当凸壳顶点个数n为偶数时，该算法的平均时间复杂度为：

n²/2−n+1+m[（n−2）/2+k]