1 
Algorithm(a-array, n-length):
      for(i=2;i<=n;i++)
         if(a[1]<a[i]) Swap(a,1,i);  
      for(i=n-1;i>=2;i--)
         if(a[n]<a[i]) Swap(a,n,i);

Swap最悪の場合、上記のコードで何回呼び出されるかを調べたいので、いくつか質問があります。

そこでの最悪のケースは何ですか？

  • 最初のforループしかない場合、このアルゴリズムの最悪のケースは、配列aがすでに昇順でソートされており、スワップがn-1回呼び出されることであると言えます。
  • 2番目のループしかない場合、最悪のケースはaがすでにソートされていることですが、今回は順序が降順になります。つまり、最初の最悪のケースを考えるSwapと、は2番目のループで呼び出されず、その逆も同様です。つまり、各反復で両方のループで呼び出すことはできません。

私は今どうすればいい？互いに反対の2つの最悪のケースをどのように組み合わせるのですか？最悪の場合は、できるだけ多くのスワップ呼び出しが必要であることを意味します。：）

PS複雑さはO（n）であることがわかりますが、スワップが実行される回数をできるだけ正確に見積もる必要があります。

編集1：Swap(a,i,j)要素a[i]とを交換しますa[j]。

4

2 に答える 2

1

sとrを、元の配列の最大要素と最大要素の隣の位置とします。最初のループの終わりに：-最大のものが最初の位置に来ます。r <sの場合、次に大きい位置はrになります。r> sの場合でも、rになります。2番目のループの終わりに、次に大きい要素が終わりになります。最初のループの場合、固定sの最悪のケースは、sまでのすべての要素が昇順である場合です。スワップの数はsです。2番目のループでは、最大の次に大きいものが配列の先頭に近い場合に最悪のケースが発生します。これは、r <sであり、最大値以降のすべての要素が元の配列で降順であった場合に発生します（最初のループの後でも変更されません）。スワップの数は、rとsに関係なく、最悪の場合はns-1 Total=n-1です。

例：A = [1 2 5 7 3 4]ここでは、最大要素7までは昇順であり、その後は降順のスワップ数= 5

于 2012-12-17T22:26:19.150 に答える
0

最初のループの最悪のケースは、すべてのaiが1≤i < j≤nのjよりも小さいことです。その場合、すべてのjが1と交換されるため、最後に1が最大数になります。このスワッピングは、最大でn -1回しか発生しません。例：

[1,2,3,4,5] ⟶ [5,1,2,3,4]

同様に、2番目のループの最悪のケースは、すべてのaiが2≤i < j≤nのjよりも大きいことです。その場合、すべてのa iがnと交換されるため、最後にanがサブ配列a2、…、anの最大数になります。このスワッピングは、最大でn -2回しか発生しません。例：

[x,4,3,2,1] ⟶ [x,3,2,1,4]

ここで注意が必要なのは、両方のループでの呼び出しの条件が相互に排他的であるため、両方の条件を組み合わせることですSwap。任意のペアa i、1≤i <j≤nおよびa i < a jの場合、最初のループは。しかし、そのようなペアのいずれについても、2番目のループは反対のことを期待しているので呼び出されません：a i > aj。SwapSwap

Swapしたがって、呼び出しの最大数はn -1です。

于 2012-12-17T22:11:18.483 に答える