8

次の入力を受け取り、次の出力を吐き出す効率的なアルゴリズムを設計するには、ヒントが必要です。

入力：それぞれ長さがnの整数AとBの2つのソートされた配列

出力：配列AとBのデカルト積で構成される1つのソートされた配列。

For Example: 

Input:
A is 1, 3, 5
B is 4, 8, 10
here n is 3.

Output:
4, 8, 10, 12, 20, 24, 30, 40, 50

これがこの問題を解決するための私の試みです。

1）出力がn ^ 2であるとすると、効率的なアルゴリズムはO（n ^ 2）時間計算量よりも優れた処理を行うことはできません。

2）最初に、単純ですが非効率的なアプローチを試しました。AとBのデカルト積を生成します。これはO（n ^ 2）時間計算量で実行できます。保存する必要があるので、並べ替えを行うことができます。したがって、O（n ^ 2）スペースの複雑さもあります。ここで、入力に仮定を行わずにO（n ^ 2logn）よりもうまく実行できないn^2要素を並べ替えます。

最後に、O（n ^ 2logn）時間とO（n ^ 2）空間複雑度アルゴリズムがあります。

入力配列のソートされた性質を利用していないので、より良いアルゴリズムがあるはずです。

4

2 に答える 2

3

O（ n²logn ）よりも優れたソリューションがある場合は、 AとBがすでにソートされているという事実を利用する以上のことを行う必要があります。この質問に対する私の答えを参照してください。

Srikanthは、これをO（n）スペースでどのように実行できるのか疑問に思っています（出力用のスペースはカウントしていません）。これは、リストを遅延生成することによって実行できます。

A=6,7,8およびB=3,4,5があるとします。まず、Aのすべての要素にBの最初の要素を掛けて、これらをリストに格納します。

6×3=18、7×3 = 21、8×3 = 24

このリストの最小の要素（6×3）を見つけて出力し、Aのその要素にBの次の要素を掛けたものに置き換えます。

7×3=21、6 ×4 = 24、8 ×3 = 24

このリストの新しい最小要素（7×3）を見つけて出力し、次を置き換えます。

6×4=24、8×3 = 24、7 ×4 = 28

等々。この中間リストにはO（ n ）スペースのみが必要であり、リストをヒープに保持する場合、各段階で最小の要素を見つけるにはO（log n）時間がかかります。

于 2010-11-28T22:35:09.850 に答える
0

Aの値にBのすべての値を掛けても、結果リストは引き続きソートされます。あなたの例では：

Aは1、3、5です

Bは4、8、10です

1 *（4,8,10）= 4,8,10

3 *（4,8,10）= 12,24,30

これで、2つのリストをマージできます（マージソートの場合とまったく同じです）。両方のリストヘッドを見て、小さい方を結果リストに入れるだけです。したがって、ここでは4、8、10などを選択します。結果= 4,8,10,12,24,30

ここで、結果リストと次の残りのリストに対して同じことを行い、4,8,10,12,24,30を5 *（4,8,10）=20,40,50とマージします。

両方のリストの長さが同じである場合にマージが最も効率的であるため、Aを2つの部分に分割してそのスキーマを変更し、両方の部分に対して再帰的にマージを実行し、両方の結果をマージできます。

マージアプローチを使用すると、Aを並べ替える必要はなく、Bだけを並べ替える必要があるため、時間を節約できることに注意してください。

于 2010-11-29T11:03:38.643 に答える