各ボルトが正確に1つのナットと一致する、異なるサイズのn個のボルトとn個のナットが与えられます。私たちの目標は、ボルトごとにマッチングナットを見つけることです。ナットとボルトはあまりにも似ているので直接比較することはできません。しかし、ナットが大きすぎる、小さすぎる、またはボルトと同じサイズであるかどうかをテストすることができます。k個のペアを見つける時間の複雑さの下限を見つける
最悪の場合、k個のマッチングペアを見つけるにはΩ（n + k log n）のナットボルトの比較が必要であることを証明します。
私はこれを行う方法を完全に困惑しています。これは、n^kノードが必要となるので、ツリーの高さにklog（n）を与えるために3-ary決定木を描きますが、 + nがどこから来るのかを理解する。ここで
は、適切な証明の基礎を形成する可能性が非常に緩やかな答えです：
あなたが新しいナットをテストするたびに、または新しいボルトを（あなたの敵を）私を聞いていると、私と仮定しますあなたに新しいナットや新しいボルトを渡してください。あなたが開始する前に、ナットとボルトをマッチングペアに分類し、ペアをそれぞれn/2のサイズの2つのヒープに分割します。最初のn/2ステップでは、あなたが求めるものに応じて、最初のヒープからナットを、または第2のヒープからボルトを渡します。だから、いつでも一致を見つけるのを遅らせることができます。少なくともn/2のマッチングを試みるまでは、ヒープのいずれかがなくなるまでナットとボルトを決して得られません。
あなたはいつもこの情報を無視することができるので、サイズ順にボルトにラベルを付けるとあなたの人生はそれほど難しくなりません。今度は、k log n未満のk個の一致がすべてのkとn> = kに対して見つかることができれば、n個の数値を比較だけでソートする問題を解決できます。ここで、数字は集合{1 、2,3 ... n}である。実際には、例えばあなただけのために働く魔法の方法を持っていても。 k < = 3とすべてnなら、まだ残っている（ラベルのない）ナットと（ラベル付き）ボルトのセットとの間で3つの一致を繰り返し見つけることで、この低比較ソートを行うことができます。したがって、log n未満の比較で一致するものを見つけることができれば、n対n未満の比較で{1,2 ... n}であることが分かっている数字をソートすることができますが、通常の情報理論上のソート数の下限は依然としてここに保持されます。したがって、少なくともk log nの比較が必要です。
ここで、max（n/2、k log n）の下限値があります。因子については気にしないので、max（n、k log n）としましょう。しかし、再び、無視する因子をn + k log nに変えることができるので、（a + b）/ 2 < = max（a、b）< = a + b
まだ少し混乱していますが、私はklognをk番目の場所に並べ替えることができますが、それで十分ではないのですか？そのような意思決定木が存在するならば、klogn比較では根から葉に達することは保証されないでしょう。最後にチェックされたボルトが合っている箇所では止血を避けることが保証されますか？ –
k log nを導き出すにあたっては、問題を簡単にすることから始めました。ラベルを付ける前と並べ替えたあとに、すべてのボルトをレイアウトしています（ボルトを互いに比較できないので、この問題ではできません）。だから、このアプローチでは、k log nは楽観的ではなく、小さなkはn/2の境界で打ち負かされます。最初の試合の時間を遅らせたいと思っている敵のための簡単な戦略を考えてみましょう。可能な限り。 – mcdowella