1つのクエリで最も軽いことを知ってn個のボールをソートする

異なる重みを持つ$ n $ボールがあり、$ b $を$ 2 $〜$ n $の整数にするとします。 $ S subset
{1,2,3、 dots、n } $を$ B $以下で設定すると、$ S
$の最も軽いボールを教えてくれるマシンがあります。目標は、$ n $ボールを重みに応じてソートし、マシンへのクエリはごくわずかです。
定数$ c $に対して、$ c
log_b(n!)$クエリを使用して解決するアルゴリズムを探します。ここで、cはbとnに依存しない絶対定数です。

ベストアンサー

対数の底を変更することは、式に定数を掛けることと同じです:log b (n!)= log
a (n!)/ log a (b)。
log a (b)は単なる定数であるため、 j log k
(n!)
定数jとkが問題を解決する(私たちは単にc = jkを置く)。
この理由から、アルゴリズムの基底は、漸近的複雑さを議論するときには通常無視される。基本的に O(log(n!)= O(n
log(n)))のアルゴリズムを探しています。

この時点で問題を解決するアルゴリズムは、 MergeSortヒープソート

などの既知のアルゴリズムがあります。

k要素のサブセット(2ではなく)で最小の数を検出するオラクルを使用するオプションは、可能なアルゴリズムを定数だけ改善します。

ボールをk個のサブセットに分割し、それぞれを再帰的にソートし、Oracleを使用してこれらのサブセットを線形時間でマージする、MergeSortを修正しました。
 しかし、これもまた、定期的なMergeSort(巡回の深さはlog 2 (n)ではなくlog
k (n) >

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です