パイプとソケットの問題

異なるサイズのn個のパイプと異なるサイズのn個のソケットのセットを考えると、パイプとソケットの間には1対1のマッピングがあります。つまり、パイプは1つのソケットにしか収まりません。パイプとソケットを正しく合わせる。

制約:パイプと別のパイプまたはソケットとの比較はできません。パイプはソケットとしか比較できず、ソケットはパイプと比べてどれが大きいか小さいかを見ることができます。

ベストアンサー

まず、以下の簡単なアルゴリズムを考えてみましょう。

任意のパイプを選択します。一致するものが見つかるまで、すべてのソケットと比較してください。その後、別のパイプに移動し、すべてが完了するまで繰り返します。

$ n $パイプと$ n $ソケットがある場合、これは最大で

$ n(n-1)/ 2 $比較。

それで最悪の場合にどれくらいの時間を取れるかについての上限が与えられます。下限については、

最初にいくつかの追加情報が与えられたとします。すべてのソケットのサイズがわかります。私たちの課題はパイプのソートです。パイプのサイズを$
1 $から$ n $に変更するだけです。可能な$
n!$個の注文があり、各比較は最大で3つの結果のうちの1つを与えます。したがって、すべての結果を区別するには少なくとも$
log_3(n!)$の比較が必要です。これは注文$ n log n $です。/p>

平均のパフォーマンスが良好なコンテンツには、これを行うことができます:

ランダムパイプを選択します。
(それをPと呼んでください)。一致するものが見つかるまで、すべてのソケットに対して試してください。
(Sと呼ぶ)パイプを「Sより小さい」、「Sより大きい」、「Pより小さい」、「Pより大きい」ソケットに分割し、その後に2つの小さなサブ問題がある。同じ方法でそれらを解決してください。
(これらが小さくなると、上の簡単なアルゴリズムに切り替えるほうが実際にはうまくいくかもしれません)。

これは平均して、

時間は$ n log n $に比例し、比例定数はあまりにも悲惨ではない。
(パーティション分割のステップが約2倍遅くなることを除けば、クイックソートと似ている)

私はまだアルゴリズムを考えていない

最悪の場合、二次的な時間より優れていますが、私はそこに1つあると確信しています。最悪の場合、$ n log n
$の時間を管理できると思う。一つの難点は、いくつかの分割スキームがソートよりもはるかに難しいことです。たとえば、mergesortのようなものを探すのは当然の考えですが、最初は$
n/2 $ 一致するパイプとソケットを見つける必要があります。

おそらく、

より困難な問題を解決する。 $ n $ pipeと$ n
$ソケットは必ずしも一致しません。元の問題と同じ比較能力を持っています。 $ a、b $が異なる型であり、$ a $が$ b
$より大きい場合、$ a $より前の$ b $を持つことができないように、それらを並べ替える必要があります。 $ O(n log
n)$で this を実行できますか?

ここでのポイントは、

より困難な問題は、より良い「帰納仮説」を作り出すかもしれない。だから、まず$ lfloor n/2 rfloor
$パイプと$ lfloor n/2 rfloor $ソケットを選びましょう。これらをソートし、残りの$ lceil n/2
rceil $パイプとソケットをソートします。今、これらを時間$ O(n)$に組み合わせることができれば、時間$ O(n
log n)$における元の問題に対する解を得る。残念ながら私たちはできません。 $ n/2 $の最大パイプと$ n/2
$の最小ソケットを選択したとします。仕事を終えるためには$ O(n log
n)$より小さい時間に行えないパイプをソートする必要があります。しかし、これらの行に沿った何かが実行可能かもしれないようです。

返信を残す

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