繰り返しのない数字を含むサイズ n の 2 つのデータベースがあります。したがって、合計で 2n 個の要素があります。一度に 1 つのデータベースへのクエリを介してアクセスできます。クエリは、ak を指定すると、そのデータベースで k 番目に小さいエントリを返すようなものです。O(log n) クエリのすべての 2n 要素の中で n 番目に小さいエントリを見つける必要があります。
アイデアは分割統治を使用することですが、これについて考える助けが必要です。ありがとう！
質問する
4013 次
3 に答える
2
少し前に資格試験でこの問題を見たのですが、宿題の匂いがします。したがって、私は次の 2 つの提案のみを行います。
ループ不変条件の正確な性質に注意して、二分探索を調べます。Jon Bentley の著書Programming Pearlsに適切な説明があります。
二分探索の不変条件を一般化してみてください。
さまざまな特殊なケースで絵を描く:
- DB1 のすべての数値は、DB2 のすべての数値よりも小さい
- 逆に
- DB1 は DB2 に等しい
- DB2 のすべての数値は、DB1 の対応する数値の 2 倍です
これはかなり難しい問題です。正しさの証明にまっすぐ進むと、より簡単に時間を過ごすことができます。
于 2010-03-27T22:37:31.207 に答える
1
これが私がこれをどのように考えたかです。教育的な問題なので、「あぁ、考えていなかったので、自分で考えてみよう」と思われる点があれば、読むのをやめることをお勧めします。
1）sdcwcと同じ観察：0から始まるか1から始まるかについてわずかな混乱が生じる可能性がありますが、データベースはソートされた配列と考えることができます。要素0を要求すると、最小になります。私は12を求めます、私は13番目に小さいです。等々。これは視覚化するのが簡単だと思います。
2）O（log n）アルゴリズムを探していることがわかっています。つまり、大まかに言えば、次の2つのいずれかを探しています。
最小の要素を計算することから始めて、次に最小の2番目、最小の4番目、8番目などを計算し、必要なサイズになるまで、各ステップを一定時間で実行します。これは私には有望に聞こえません。
または、サイズnの問題から始めて、サイズn / 2の問題を解くことにより、元の問題を解くことができる定数時間演算を実行します。明らかに、n = 1の問題を一定時間で解決して、アルゴリズムを完成させることができます。これはもう少しもっともらしいように聞こえます。
実際には、毎回n/2である必要はありません。n / 3、または999 * n / 1000の場合もありますが、結果はO（log n）のままです。ただし、最初にn/2を探しても害はありません。
3）そのような問題をどのように減らすつもりですか？さて、一方の配列の先頭からm個の要素を割引/削除して、k番目に小さいものよりも小さい場合、結果の配列のペアの（km）番目に小さい要素を見つけることができます。元の配列のk番目に小さい。
4）最後に、画期的な観察結果は、配列Aのm番目に小さい要素が配列Bのm番目に小さい要素よりも小さい場合、Aのそのm番目の要素が2つの配列の（2m）番目に小さい要素になることはないということです。最大で2*（m- 1）両方の配列を組み合わせた場合よりも厳密に小さい要素。
私が間違いを犯さない限り、残りはコーディングです。kが奇数の場合のオフバイ1を説明するための小さな追加の引数を使用すると、この解は実際にはO（log k）になります。これは、k <= 2 * nであるためO（log n）です。
于 2010-03-28T11:07:47.083 に答える
1
チップ：
- 「データベース」が実際には2つのソートされた配列であることを確認してください。
- 配列の「中間」から要素を取り出して比較します。比較の結果により、一部を「除外」できる場合があります。
于 2010-03-28T01:28:41.853 に答える