运行时间分析，三个内for循环

这是我的第一个问题，我敢肯定，我也会接受我的第一个答案：P运行时间分析，三个内for循环

我必须做的一个算法的渐进分析，从一个数组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循环我有期望至少Ø的运行时间（n^2），与第三内的循环，我会得到这样的O（N * N * [ ??]）。第三for循环执行每次J-i + 1个的操作和仅对于i < = j的。矩阵将具有，第二的第一个元素等于0，然后计算平均值...

最终矩阵将导致几乎一半填充（但不是N/2）所以，填充有平均计算的第一行对于第三循环中的值不为[N/2]

如何可以计算用于最里面For和也运行时间为整个算法的运行时间？

来源

2013-03-07 Daved

对我来说，它仍然看起来像（大约）N/2为最内圈。 – 2013-03-07 21:39:55

是的，但整个矩阵仍然可以为O通过消除第三环路建（N^2）的时间（和保持A的运行总和[1] ... A [J]）。 – 2013-03-07 21:46:34

在这种情况下，我可以说运行时间是O（N^3）？对于算法分析来说这是一个可以接受的估计？ – Daved 2013-03-07 21:48:26

你可以尝试只计算的时间内循环语句被执行的数量。

您遍历i从1到N.现在你只会做内环路（含总和）当j大于或等于N所以Ĵ循环从我到N.内最环路，则包括ji补充。在你得到的（在枫树语法）

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

然后，您需要考虑到M [i] [j]，这是做了N^2次的分配。

以前是指令的总量。然而，如果你只是在寻找整体的复杂性，那么你应该看到内部循环依赖于N，这会给你O（N^3）的整体复杂性。

请注意，该代码可以通过从一开始就存储A [1]总和避免了内部循环的复杂性和不尝试每次都重新计算它们

来源

2013-03-07 21:50:22 Origin

小错字：-1/6 * N^3应该是1/6 * N^3。 – anumi 2013-03-07 22:26:28

运行时间分析，三个内for循环

回答

相关问题