ショートギャップと平均ギャップ

Question

任意の実数のソートされた配列A [1 ... n]が与えられた場合 各i∈[1 ... n-1]に対して、 （Oで： - [I + 1] [I] A.

のi番目のギャップは、A）A. --try 1のN-1個のギャップの平均ギャップを計算されn）時間、Aを繰り返し、各ギャップを 'GapSum'に追加します。 GapSum/n-1 =平均ギャップ

b）Aのi番目のギャップが平均このようなi番目のギャップは、ショートギャップと呼ばれます。 A. の短いギャップを見つけてください - 試してください1：明らかにO（n） - 各ギャップを確認し、最小値を返します。 Aの短いギャップを見つけるために、漸近的に速い分裂と征服のアルゴリズムがありますか？

私はこれをもっと速くする方法について固執していますか？おそらく私が見過ごしている平均的な資産がありますか？どんな方向にも役立ちます。

--edit-- Nicoは、平均ギャップが一定時間内に計算できるとコメントしました。 これは一定時間としてカウントされますか： 一定の時間内の平均ギャップを計算できる唯一の考え方は、計算前に補助配列を準備して、B [i]までのギャップの合計を格納することです。次いで、平均ギャップが一定時間のルックアップがあり、nを知って、あなたは一定の時間で平均空隙サイズを計算することができ、Aがソートされていることを考えるとB [N-1]/N-1

Answer 1

1. あろう計算最初の要素と最後の要素の差をとり、nで割ることによって計算されます。

2. a。 Aを繰り返し、の最初ののギャップを平均値以下に戻します。最小のギャップを見つける必要はありません。あなたの実行時間はまだO(n)になります。

   b。あなたはより良くできますか？ binary searchと同様のことを行うことを検討してください。アレイの2つの半分の平均ギャップサイズを計算します。平均値の低いものには少なくとも1つの短いギャップが含まれていなければならないので、その半分の範囲内で検索することができます。その半分で再帰的に同じことをして、O(log n)アルゴリズムで終わるかもしれません！