短差距与平均差距
Short Gap vs Average Gap
给定一个由任意实数组成的排序数组 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) -- 检查每个间隙，return 最小。
是否有渐近更快的分而治之算法来找到 A 的短间隙？
我有点不知如何才能更快地做到这一点？是否有 属性 个平均值是我可能忽略的。任何方向都会有所帮助。
--编辑--
Nico 评论说平均差距可以用常数时间计算。
这算作恒定时间吗：
我必须能够在恒定时间内计算平均间隙的唯一想法是在计算之前准备一个辅助数组，它将间隙的总和存储到 B[i] 中的 i。然后计算平均差距将是 B[n-1]/n-1
鉴于 A 已排序，进行恒定时间查找并且您知道 n，您可以通过取第一个和最后一个元素并除以 n.
一个。遍历 A 和 return 第一个 差距小于或等于平均值。无需寻找最小的间隙。不过，您的 运行 时间仍会在 O(n) 内。
b。你能做得更好吗？考虑做类似于 binary search 的事情：计算数组两半的平均间隙大小。平均值较低的那一个必须至少包含一个短间隙，因此您只能在那一半内进行搜索。在那一半递归地做同样的事情，你可能会得到一个 O(log n) 算法！
给定一个由任意实数组成的排序数组 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) -- 检查每个间隙，return 最小。 是否有渐近更快的分而治之算法来找到 A 的短间隙？
我有点不知如何才能更快地做到这一点？是否有 属性 个平均值是我可能忽略的。任何方向都会有所帮助。
--编辑-- Nico 评论说平均差距可以用常数时间计算。 这算作恒定时间吗： 我必须能够在恒定时间内计算平均间隙的唯一想法是在计算之前准备一个辅助数组，它将间隙的总和存储到 B[i] 中的 i。然后计算平均差距将是 B[n-1]/n-1
鉴于
A已排序，进行恒定时间查找并且您知道n，您可以通过取第一个和最后一个元素并除以n.一个。遍历
A和 return 第一个 差距小于或等于平均值。无需寻找最小的间隙。不过，您的 运行 时间仍会在O(n)内。b。你能做得更好吗？考虑做类似于 binary search 的事情：计算数组两半的平均间隙大小。平均值较低的那一个必须至少包含一个短间隙，因此您只能在那一半内进行搜索。在那一半递归地做同样的事情，你可能会得到一个
O(log n)算法！