3

質問は次のとおりです。

同じ長さ n を持つ 5 つのソートされたリスト A、B、C、D、E があります。問題は、この 5 つのリストの中央値を O(logn) 時間で計算できるアルゴリズムを見つけることです。私は一般的なアイデアを考えていますが、それが必要とする正確な複雑さを理解できませんでした.

A、B、C、D、E の中央値が a、b、c、d、e で​​あるとします。そして、私たちは持っていa<b<c<d<eます。配列 A の前半と配列 E の後半を破棄できることは明らかです。これで、5 つの新しい配列ができました。B、C、D は同じままで、それぞれに n 個の数字があります。A' と E' にはそれぞれ n/2 個の数が残っています。次に、A' と E' の中央値を a' と e' として計算し、それらを b、c、d と比較します。5つの中央値の新しい順序a'<b<e'<c<dが中央値。プロセスは続きます...

アルゴリズムはO(logn)という感じです。しかし、正確な証拠はわかりません。最初のログイン手順では、5 つのリストの残りの番号をすべて合計すると、候補番号を確実に 3n に減らすことができます。最初に n 個の数字を追い出し、2 回目は少なくとも n/2 個の数字、3 回目は n/4 個の数字などを追い出します。しかし、残り3nを取得した後の解析方法がわかりません。

このアルゴリズムで実際に O(logn) を取得できますか?

4

1 に答える 1

2

はい、実際にできます。それらのステートメントを見てください

  • リストが 1 つしかない場合にのみ、最終結果を取得できます。少なくとも 2 つのリストがなければ、これについて話すことはできません。
  • アルゴリズムのすべてのステップで、半分の 2 つのリストを削減しています。リストに要素が 1 つしかない場合は、リスト全体を削除しています。
  • リストを削除するのに何ステップかかるか数えてみましょう。最初の削除では n/2 個のアイテムを削除し、2 回目は n/4 個というように、最終的にリストを削除するときに 1 つの要素が残るまで削除します。約 log(n) 操作が必要です (実際に log(n) か log(n)+1 かはわかりませんが、どちらの場合も O(log(n)) です)。
  • したがって、5 つのリストを削除する必要があります (最後のリストで中央値を見つける操作は、リストを減らす操作に一般化できます)。それらの 1 つを排除するには O(log(n)) が必要なので、O(log(n)) でもすべてを実行します。原因 5 は定数です。
于 2012-01-30T02:10:09.700 に答える