0

明日の中間試験に向けて勉強していますが、これらの時間の複雑さに苦労しています。本の簡単な例と、この例について説明します

交換ソート

void exchangesort (int n, keytype S[])
{
  index i, j;
  for(i=1; i<=n-1; i++)
    for(j=i+1; j<=n; j++)
      if(S[j] < S[i])
        exchange S[i] and S[j];
}

この Exchange の並べ替えの「Every-Case Time Complexity」についてjは、基本的な操作 (交換) があるため、for ループを分析する部分がほとんど理解できます。したがって、パスの総数をリストすると、次のようになります。

T(n) = (n-1) + (n-2) + (n-3) + ... + 1 = (n-1)n/2

今私の質問は... 1 はどこから来たのですか? だと思いましたn-1 + n-2 +... + n。

さらに、私が本当に理解していないのは、(n-1)n/2.
それは明らかに私が中期的に考え出さなければならないものであり、それを見ると、直感的には思い浮かびません..など(n-1)n/2を思いつく方法を理解しています.T(n) = (n-1) + (n-2)

明日の中間試験でこのような答えを思いつくことができるように、誰かがこれを素人の言葉で説明してもらえますか?

4

4 に答える 4

4

内側のループでjは、 からi+1までn、つまりn-i値を通して実行されます。したがって、全体として、

sum_{i = 1 to n-1} (n-i)

ステップ、(n-1) + (n-2) + ... + (n - (n-1)) = (n-1) + (n-2) + ... . 1。

さて、最初のk正の整数の合計には、閉じた式があります。

k*(k+1)/2

ここで、k = n-1.

最初の正の整数の合計の式を計算するには、ロバート キングの回答kで述べたように、いくつかの優れた方法があります。伝えられるところによると、ガウスは 5 歳のときに最初の方法でそれを解決し、教師は生徒たちに 1 から 100 までの整数の合計を計算するタスクを与え、数分間の静かな時間を持つことを望んでいました。次のように配置されているかどうかを確認することをお勧めします。

  1   +   2   + ... + (n-1) +   n
  n   + (n-1) + ... +   2   +   1
----------------------------------
(n+1) + (n+1) + ... + (n+1) + (n+1) = n*(n+1)
于 2012-02-08T19:58:49.460 に答える
1

それを解決する1つの方法は次のとおりです。

合計=1+2+3+4+...+n

2*合計 = 1+2+3+4+...+n + 1 + 2 + 3 + 4 +...+n = 1+(n) + 2+(n-1) + 3+(n -2)..+ (n)+1

2*合計=1+n + 1+n + 1+n...

2*合計 = n(1+n)

合計=n*(n+1)/2

しかし、これを理解する簡単な方法は、正方形またはグリッド マトリックスを想像することです。

i が新しい行ごとに下がると、j は行列の対角線に向かい、余分な列になります (i<=j .. j が対角線を越えられないことがわかっているため)。これは、すべての演算が行列の対角線の片側にある (i,j) の組み合わせであることを意味します。したがって、操作の数は、マトリックス全体の面積の半分になります。行列が an*n 行列の場合、約 n*n/2 の領域があります (ただし、対角線を 2 倍に数えることはできないため、実際には n*(n-1)/2 になります)

于 2012-02-08T20:02:03.440 に答える
0

次のように考えてください。

When i = 1, inner loop runs (n - 1) times [j = 2 to n]
When i = 2, inner loop runs (n - 2) times [j = 3 to n]
When i = 3, inner loop runs (n - 3) times [j = 4 to n]
....
When i = k, inner loop runs (n - k) times [j = k + 1 to n]
...
When i = n - 1, inner loop runs (n - (n - 1)) = 1 time [j = n to n]

それらを要約してください：

(n - 1) + (n - 2) + (n - 3) + ... + 1 = n(n - 1) / 2

最悪の場合、何度exchangeも実行されn(n - 1) / 2ます。

于 2012-02-08T19:57:50.630 に答える
0

級数は (n-1) から (1) [(n-1), (n-2) ... (n-(n-1))]になります派生。その非常に理解しやすいです。

于 2012-02-08T19:59:45.080 に答える