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]

考虑到给出前两个 for 循环，我必须期望至少运行时间为 O(n^2)，而第三个内部 for 循环我会得到类似 O(N*N*[??]) 的东西。第三个 for 循环每次执行 j-i+1 次操作，并且只针对 i<=j。矩阵的第一行将填充计算的平均值，第二行是第一个元素等于 0，然后是计算的平均值......

最终的矩阵将几乎填充一半（但不是 N/2）所以第三个循环的值不是 [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) 的总体复杂性。

Do note that the code could avoid the inner loop complexity by storing the A[i] sums from the start and don't try to recalculate them every time

于 2013-03-07T21:50:22.627 回答