0

私は複雑性理論のコースを取っているので、問題がある数学的背景が必要です。だから私はいくつかの練習をしようとしている間、私は次の例で立ち往生しています

1)  for (i = 1; i < n; i++) {
2)      SmallPos = i;
3)      Smallest = Array[SmallPos];
4)      for (j = i+1; j <= n; j++)   
5)          if (Array[j] < Smallest) {
6)              SmallPos = j;
7)              Smallest = Array[SmallPos]  
            }   
8)       Array[SmallPos] = Array[i];
9)       Array[i] = Smallest;
    }

したがって、合計計算時間は次のようになります。

T(n)    = (n) + 4(n-1) + n(n+1)/2 – 1 + 3[n(n-1) / 2]
        = n  + 4n - 4 + (n^2 + n)/2 – 1 + (3n^2 - 3n) / 2
        = 5n - 5 + (4n2 - 2n) / 2
        = 5n - 5 + 2n^2 - n
        = 2n^2 + 4n - 5 
        = O(n^2)

そして、 n(n+1)/2 – 1に分析された4行目と5行目 3[n(n-1) / 2]について、私が理解していない、または混乱していること 。正の系列の合計が =n(first+last)/2であることは知っていましたが、理解したとおりに計算しようとすると、異なる結果が得られます。私は行番号4を計算するので、n(first+last)/ 2に従って=n((n-1)+2)/2になるはずですが、ここではn(n+1)/2 – 1です。3[n(n-1) / 2]についても同じ.....これもわかりません

また、ここに分析に書かれているものがあります。誰かが私に説明できると助かります。

ステートメント 1 は n 回 (n - 1 + 1) 実行されます。ステートメント 2、3、8、および 9 (それぞれ O(1) 時間を表す) は、外側のループを通過するたびに 1 回、それぞれ n - 1 回実行されます。i = 1 でこのループを最初に通過すると、ステートメント 4 が n 回実行されます。ステートメント 5 は n - 1 回実行され、配列の要素が降順であるという最悪のケースを想定すると、ステートメント 6 と 7 (それぞれ O(1) 回) が n - 1 回実行されます。

i = 2 の外側のループの 2 回目のパスでは、ステートメント 4 が n - 1 回実行され、ステートメント 5、6、および 7 が n - 2 回実行されます。したがって、ステートメント 4 が実行されます (n) + (n -1) +... + 2 回実行され、ステートメント 5、6、および 7 が (n-1) + (n-2) + ... + 2 + 1 回実行されます。最初の合計は n(n+1)/2 - 1 に等しく、2 番目の合計は n(n-1)/2 に等しくなります。

したがって、合計計算時間は次のようになります。

T(n)    = (n) + 4(n-1) + n(n+1)/2 – 1 + 3[n(n-1) / 2]
        = n  + 4n - 4 + (n^2 + n)/2 – 1 + (3n^2 - 3n) / 2
        = 5n - 5 + (4n2 - 2n) / 2
        = 5n - 5 + 2n^2 - n
        = 2n^2 + 4n - 5 
        = O(n^2)

この例を含むファイルへのリンクは次のとおりです: http://www.google.com.eg/url?sa=t&rct=j&q=Consider+the+sorting+algorithm+shown+below.++Find+the+number+ of+instructions+executed+&source=web&cd=1&cad=rja&ved=0CB8QFjAA&url=http%3A%2F%2Fgcu.googlecode.com%2Ffiles%2FAnalysis%2520of%2520Algorithms%2520I.doc&ei=3H5wUNiOINDLswaO3ICYBQ&usg=AFQjCNEBqgrtQldfp6eqdf6

4

1 に答える 1

1

4行目：分析によると、実行n+(n-1)+...+2回数です。これは(n-1)用語の合計です。使用する式でn(first+last)/2、、は項の数をn表します。数式を用語のシーケンスに適用する場合は、である必要があります。n-1(n-1)((n)+(2))/2=(n²+n-2)/2=n(n+1)/2-1

5行目：同じ式を使用できます。分析が言うように、あなたは計算しなければなりません(n-1)+...+1。これはn-1用語の合計であり、最初と最後がn-1と1です。合計はによって与えられ(n-1)(n-1+1)/2ます。ファクター3は、それぞれが実行されている3つの行（5、6、7）からのものです(n-1)(n)/2。

于 2012-10-06T22:08:50.283 に答える