AO(n*log(n))算法用于找到具有最低斜率的段(在n*n个段中)

Question

给定定义n ²行的不同点的P = {p ₁,...,p _n },写一个算法,该算法在最坏的情况下找到具有最低斜率(最小绝对值)和时间复杂度的行.O(n*log(n))

Answer 1

基于y位置对点进行排序(使用任意数量的众所周知的算法,n log n time).按顺序浏览列表,从0到n - 1,比较每个点对的斜率与您发现的任何斜率到目前为止的最低斜率.(那是时候了).

总的来说,那将是O(n log n).

在伪代码中:

Let P be the list of points (this list starts at 1)
n = P.length
S = quicksort("a.y < b.y", P) // or some other O(n log n) algorithm
bestSlope = float.inf
let p1 and p2 be points
for i = 1 to n-1:
    currSlope = abs((P[i].y - P[i+1].y) / (P[i].x - P[i+1].x))
    if currSlope < bestSlope:
        bestSlope = currSlope
        p1 = P[i]
        p2 = P[i+1]

Answer 2

定理:

• 给定一组点P.
• 在P中选择两个点A和C,使得AC线具有最小的绝对斜率(如问题中所定义).
• 对于多对点具有相同斜率的退化情况,让AC成为具有该斜率的最短线段.
• 然后P中没有其他点,A和C之间有Y坐标.

证明(矛盾):

• 假设至少有一个其他点B,其Y坐标在A和C之间.
• 然后存在三种可能的情况:
  • B是共线A和C.然后,线AB或BC具有相同的斜率AC,但两者都是比AC短.矛盾.
  • B落在"以上"AC的半平面上.然后,线AB具有比AC更浅的斜率.矛盾.
  • B落在"下方"AC的半平面上.然后,线BC具有比AC更浅的斜率.矛盾.
• 所有情况都会导致矛盾,因此A和C之间不会出现任何问题.
• QED.

有了这个定理,你可以清楚地使用@ Zshazz的算法来找到正确的对 - 因为它们将是最近的邻居 - 在O(n*log n).