短間隙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

回答