短间隙VS平均间隙

给定一个排序后的数组A [1 ... n]的任意的实数对每个i∈[1 ... N-1]的; A [1 + 1] - A [i]为A的第i个间隙短间隙VS平均间隙

a）计算A. 的n-1个间隙的平均间隙--Try 1：在O（ n）时间，迭代A并将每个差距添加到'GapSum'。 GapSum/n-1 =平均差距

b）根据平均法，必定存在一些i∈[1 ... n-1]，使得A的第i个间隔不超过平均值答：任何这样的第i个差距都称为短缺。找到一个短的差距A. - 尝试1：明显的O（n） - 检查每个差距，返回最小。是否有一个渐近更快的分裂和征服算法来找到A的短缺？

我是一种坚持，我怎么能做到这一点得更快？是否有我可能忽略的平均值的属性？任何方向都会有帮助。

- 编辑 - 尼科评论说，平均间隙可在恒定的时间来计算。这会算作恒定时间：我必须能够计算在固定时间内的平均间隙的唯一的想法是，它存储的间隙的总和高达i的B [I]计算之前准备一个辅助阵列。然后计算平均间隙。将B [N-1]/n-1个

2017-04-12 RYS221

你尝试过什么？在SO上不鼓励任何研究工作而倾销你的作业。顺便说一句，平均差距可以在不变的时间内计算出来。 –

到目前为止，我唯一能提出的两种解决方案是我描述的2 O（n）时间方法。我一直在尝试一段时间想出一种更快速的方法，但失败了。 – RYS221

我需要一个提示/方向。如果我们需要所有间隙值来计算平均值，平均值如何计算？ – RYS221

鉴于A进行排序，具有恒定时间的查找，你知道n，可以计算在固定时间的平均间隙尺寸通过取第一个和最后一个元素之间的差值除以n。
一个。迭代通过A并返回第一个间隔小于或等于平均值。没有必要找到最小的差距。不过，你的运行时间仍然在O(n)之内。

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

2017-04-12 07:30:13

回答