algorithm - 短差距与平均差距

Question

给定一个由任意实数组成的排序数组 A[1...n]对于每个 i ∈ [1 ... n-1]； A[i+1] - A[i] 是 A 的第 i 个间隙。

a) 计算 A 的 n-1 个间隙的平均间隙。--尝试 1: 在 O(n) 时间内，迭代 A 并将每个间隙添加到“GapSum”。GapSum/n-1 = 平均差距

b) 根据平均定律，必须存在一些 i ∈ [1 ... n-1] 使得 A 的第 i 个间隙不超过 A 的平均间隙。任何这样的第 i 个间隙称为短间隙。找到 A 的短间隙。--尝试 1:明显 O(n) -- 检查每个间隙，返回最小值。是否有渐进更快的分而治之算法来找到 A 的短间隙？

我有点不知如何才能更快地做到这一点？是否有我可能忽略的平均值属性。任何方向都会有所帮助。

--编辑--Nico 评论说平均差距可以用常数时间计算。这算作恒定时间吗:我必须能够在恒定时间内计算平均间隙的唯一想法是在计算之前准备一个辅助数组，它将间隙的总和存储到 B[i] 中的 i。然后计算平均差距将是 B[n-1]/n-1

Answer 1

1. 鉴于 A 已排序，具有恒定时间查找并且您知道 n，您可以通过取差来计算恒定时间内的平均间隙大小在第一个和最后一个元素之间除以 n。

2. 一个。遍历 A 并返回小于或等于平均值​​的第一个 间隙。无需寻找最小的间隙。不过，您的运行时间仍将在 O(n) 内。

   你能做得更好吗？考虑做类似于 binary search 的事情:计算数组两半的平均间隙大小。平均值较低的那一个必须至少包含一个短间隙，因此您只能在那一半内进行搜索。在那一半递归地做同样的事情，你可能会得到一个 O(log n) 算法!