0

これは私の最初の質問であり、最初の回答も受け取ると確信しています :P

配列から、次で与えられる値を含むA[1...n]行列を計算するアルゴリズムの漸近分析を行う必要があります。M[n][n]M[i][j]

M[i][j] = (A[i] + ... + A[j])/(j-i+1), if i<=j

と

M[i][j] = 0, if i>j


for i=1 to N do                [N]
   for j=1 to N do             [N]
    if(i<=j)                   [cost]
      start=i                  [cost]
      end=j                    [cost]
      sum=0                    [cost]
      for a=start to end do    [??]
         sum += A[a]           [cost]
      M[i][j]=sum/(j-i+1       [cost]
    else                       [cost]
      M[i][j]=0                [cost]

最初の 2 つの for ループを指定すると、少なくとも O(n^2) の実行時間を期待する必要があります。3 番目の内側の for ループでは、O(N*N*[??]) のような結果になります。3 番目の for ループは、j-i+1 操作のたびに、i<=j に対してのみ実行されます。マトリックスには、最初の行に計算された平均が入力され、2 番目の行に最初の要素が 0 に等しくなり、次に計算された平均が入力されます...

最終的な行列は、ほぼ半分が満たされた結果になります (ただし、N/2 ではありません)。したがって、3 番目のループの値は [N/2] ではありません。

最も内側の For の実行時間とアルゴリズム全体の実行時間を計算するにはどうすればよいですか?

4

1 に答える 1

0

内側のループ ステートメントが実行される回数を計算することもできます。

i を 1 から N までループします。ここで、j が N 以上であるため、j が i から N までループする場合にのみ、(合計を使用して) 内側のループを実行します。最も内側のループは、ji の追加で構成されます。あなたが得るすべてで（メープル構文で）

sum(sum(j-i,j=i..N), i=1..N)= 1/6*N^3-1/6*N

次に、N^2 回行われる M[i][j] の割り当てを考慮する必要があります。

前は指示の合計量でした。ただし、全体的な複雑さだけを探している場合は、内側のループが N に依存しているため、全体的な複雑さが O(N^3) になることがわかります。

コードは最初から A[i] の合計を格納することで内部ループの複雑さを回避できることに注意してください。毎回それらを再計算しようとしないでください。

于 2013-03-07T21:50:22.627 に答える