如果每个点的每个坐标都是有理数，则凸包的时间复杂度为 O(n)

证明凸包为n平面上的点可以计算为O(n)如果每个点的每个坐标都是 p/q 形式的有理数，并且 p 和 q 有界值，则时间。

Note: 这是一个家庭作业问题。我只能想到通过某种方式避免扫描所有点来使用贾维斯·马奇。也许这可以通过向固定方向投射光线（使用有理条件）来检查下一个点存在的位置来完成.

不要使用 Jarvis March 因为它的时间复杂度为O(nh)。在最坏的情况下，h可能大到n。注意h是船体上的点数。

相反，您应该使用，例如，格雷厄姆扫描 http://en.wikipedia.org/wiki/Graham_scan其时间复杂度为O(nlogn)。在格雷厄姆扫描算法中，时间复杂度主要取决于对所有点进行排序的时间复杂度。请注意，基于比较的排序算法的时间复杂度为O(nlogn).

在你的家庭作业问题中，你可以使用基数排序 http://en.wikipedia.org/wiki/Radix_sort而不是任何基于比较的排序算法来击败上限O(nlogn)因为假设这些点的坐标都是有界的。请注意，当要排序的输入是有界基数排序时，可以使用其复杂度为O(n).

See here http://en.wikipedia.org/wiki/Convex_hull_algorithms用于比较各种凸包算法。