2

O(1) 時間で次の操作を実行できる整数の外部配列があります。

  1. get(int i) - 外部配列のインデックス 'i' の値を返します。
  2. reverse( int i, int j) - インデックス位置 i と j (i と j を含む) の間の配列の逆を返します。

逆の例: 配列 {1,2,3,4,5} を考えてみましょう。reverse(0,2) は {3,2,1,4,5} を返し、reverse(1,4) は {1,5,4,3,2} を返します。

外部配列をソートするコードを記述します。コードの時間と空間の複雑さに言及してください。

明らかに、クイックソートまたはマージソートを使用して nlogn でソートできます。しかし、シーンリオを考えると、もっとうまくやれるでしょうか?

4

4 に答える 4

3

配列を並べ替えるとは、配列を並べ替えた状態に戻す順列またはシャッフルを見つけることです。つまり、アルゴリズムは、n!可能な順列のどれを適用する必要があるかを判断し、それを適用します。あなたのアルゴリズムは、はい/いいえの質問 (セルはセルiよりも小さいか大きいjか) を尋ねることによって配列を探索するため、深さを持つ暗黙の決定木に従いますlog(n!) ~ n*log(n)。

これは、配列をソートする方法を決定するためにがO(n*log(n))呼び出されることを意味します。get()

興味深い変種は、reverse()必要な順列がわかったら、配列をソートするために必要な の呼び出しの最小数を決定することです。この数は よりも小さいことがわかっていn-1ます。これは、選択ソートを使用して達成できます。最悪の場合の数値は よりも小さくなる可能性がありn-2ますか? わからないと言わざるを得ない…

于 2012-06-26T07:34:47.467 に答える
2

swaps()問題を古典的なソートアルゴリズムに還元しようと思います。

以下では、一般性を失うことなく仮定します:j>=i各 について、反転された部分配列は、要素が 3 つ以下の場合にのみエッジを交換して いることに
注意してください。次に、「中間」を逆にして元に戻すと、次のようになります。swap(i,j) = reverse(i,j)j <= i+2
j>i+2reverse()swap(i,j) = reverse(i,j) ; reverse(i+1,j-1)

ビルドしたばかりの を使用すると、 であるquicksortswap()など、スワップを使用する比較ベースのアルゴリズムを使用できます。それぞれに最大 2 つの opsが必要なため、複雑さが残ります。O(nlogn)O(nlogn)swap()reverse()O(1)

編集:注: このソリューションは、解決策を要求した元の質問 (編集される前) に適合し、クイックソート/マージソートよりも最適化しないでください。

于 2012-06-26T07:07:32.180 に答える
1

外部操作の数を最小限に抑えたいと仮定すると、次のようになりgetますreverse。

  • getn回呼び出して、すべての整数を内部配列に読み込みます
  • 内部ソートを実行し (n log in internal ops)、順列を計算します
  • reverse最大 n 回呼び出して外部配列をソートする

これには、O(n) 時間と O(n) 空間の複雑さがあります。

匿名の反対票に応じて編集します。時間の複雑さについて話すときは、どの操作をカウントするかを常に述べる必要があります。ここでは、外部操作のみにコストがかかると仮定しました。

于 2012-06-26T07:07:32.617 に答える
0

get(int i) と reverse(int i, int j) に基づいて、コードを最適化できません。同じ複雑さになります。

于 2012-06-26T07:10:39.310 に答える