23

私の教授がクラスで示した問題を、私の O(n*log(n)) ソリューションで提示しています。

番号のリストが与えられた場合、次の回数n実行します。n-1

  • リストから2つの最小要素を抽出してx,y提示します
  • 新しい番号zを作成します。ここでz = x+y
  • リストzに戻す

O(n*log(n))、および のデータ構造とアルゴリズムを提案してくださいO(n)

解決：

最小限のヒープを使用します。

ヒープを作成するのは 1 回だけで、O(n) かかります。その後、2 つの最小要素を抽出すると O(log(n)) かかります。ヒープに配置zすると、O(log(n)) がかかります。

上記のn-1時間を実行すると、次の理由から O(n*log(n)) かかります。

O(n)+O(n∙(logn+logn ))=O(n)+O(n∙logn )=O(n∙logn )

しかし、どうすればO(n)でそれを行うことができますか?

編集：

x,y「リストから2つの最小要素を抽出して提示する」と言うことで、つまりprintf("%d,%d" , x,y)、xとyは現在のリストの最小要素です。

4

4 に答える 4

12

これは完全な答えではありません。しかし、リストがソートされていれば、問題は簡単に実行できますO(n)。それを行うには、すべての数字をリンクされたリストに配置します。頭へのポインターを維持し、途中でどこかに。各ステップで、先頭の 2 つの要素を先頭から取り出して出力し、合計が必要な場所まで中央のポインターを進め、合計を挿入します。

開始ポインタはほぼ回2n移動し、中央ポインタは約n回移動し、n挿入されます。これらの操作はすべてなO(1)ので、合計はO(n)です。

一般に、時間でソートすることはできませんがO(n)、できる特殊なケースがいくつかあります。そのため、場合によっては実行可能です。

もちろん、一般的なケースは時間内に解決できませんO(n)。なぜだめですか？出力が与えられると、O(n)やがてプログラムの出力を実行し、ペアごとの合計のリストを順番に作成し、それらを出力から除外できます。残っているのは、元のリストの要素を並べ替えたものです。これにより、O(n)一般的なソートアルゴリズムが得られます。

更新:出力 (10, 11), (12, 13), (14, 15), (21, 25), (29, 46) から入力リストに移動する方法を示すように求められました。 秘訣は、常にすべてを整理しておくことです。そうすれば、見た目がわかります。正の整数を使用すると、次に使用する合計は常にそのリストの先頭になります。

Step 0: Start
  input_list: (empty)
  upcoming sums: (empty)

Step 1: Grab output (10, 11)
  input_list: 10, 11
  upcoming_sums: 21

Step 2: Grab output (12, 13)
  input_list: 10, 11, 12, 13
  upcoming_sums: 21, 25

Step 3: Grab output (14, 15)
  input_list: 10, 11, 12, 13, 14, 15
  upcoming_sums: 21, 25, 29

Step 4: Grab output (21, 25)
  input_list: 10, 11, 12, 13, 14, 15
  upcoming_sum: 29, 46

Step 5: Grab output (29, 46)
  input_list: 10, 11, 12, 13, 14, 15
  upcoming_sum: 75
于 2012-06-19T02:59:52.980 に答える
2

これは一般的なケースでは不可能です。

問題ステートメントは、配列を単一の要素に縮小し、合計n-1の縮小操作を実行する必要があることを示しています。したがって、実行される削減操作の数はO（n）のオーダーです。O（n）の全体的な実行時間を達成するには、各削減操作をO（1）で実行する必要があります。

削減操作を明確に定義しました。

  • 配列内の2つの最小要素を削除して印刷してから、
  • それらの要素の合計を配列に挿入します。

データ構造がソートされたリストである場合、O（1）時間で2つの最小要素を削除するのは簡単です（リストの最後からそれらをポップします）。ただし、O（1）に要素を再挿入することはできません（一般的な場合）。SteveJessopが指摘したように、O（1）時間でソートされたリストに挿入できる場合、結果の操作はO（n）ソートアルゴリズムを構成します。しかし、そのような既知のアルゴリズムはありません。

ここにはいくつかの例外があります。数値が整数の場合、「基数挿入」を使用してO（1）挿入を実現できる場合があります。数直線で数の配列が十分にまばらである場合、O（1）で挿入点を推測できる可能性があります。他にも多くの例外がありますが、それらはすべて例外です。

この答え自体はあなたの質問に答えるものではありませんが、答えを正当化するのに十分な関連性があると私は信じています。

于 2012-06-19T01:32:52.753 に答える
1

値の範囲が n 未満の場合、これは O(n) で解決できます。

1>値の範囲に等しいサイズの配列mkを作成し、すべてゼロに初期化します

2> 配列をトラバースし、配列要素の位置で mk の値をインクリメントします。つまり、配列要素が a[i] の場合、mk[a[i]] をインクリメントします。

3) n-1 操作のそれぞれの後に回答を提示するには、次の手順に従います。

次の 2 つのケースがあります。

ケース 1 : a[i] がすべて正の場合

        traverse through mk array from 0 to its size
        cnt = 0
        do this till cnt doesn't equal 2
          grab a nonzero element decrease its value by 1 and increment cnt by 1
        you can get two minimum values in this way
        present them 
        now do mk[sum of two minimum]++

ケース 2 : a[i] の一部が負の場合

        <still to update>
于 2012-06-19T12:37:14.800 に答える
0

O(nlogn) は簡単です。ヒープ、トレプ、またはスキップリストを使用するだけです。

O(n) は難しそうですね。

https://en.wikipedia.org/wiki/Heap_%28data_structure%29
https://en.wikipedia.org/wiki/Treap
https://en.wikipedia.org/wiki/Skip_list
于 2012-06-26T03:56:55.450 に答える