总结运行时分析

Question

A[]为n的大小，B[][]为nxn的大小

for i_{1,n} {
 for j_{1,n} {
  if(i<=j) -> B[i,j] = sum of the elements A[i], A[i+1],...,A[j]
  else -> B[i,j] = 0

我理解前2个for循环是n次迭代。我的问题是如何做(i<=j)部分。在最大情况下，它将求和n次(当i = 1且j = n时)。在最小情况下，它将只做一件事，因此为1。

我真的真的迷路了

Answer 1

我对这些理论性的运行时分析很不在行，但这可能有助于从另一个角度看问题:

for i_{1,n}
{
    if (j>i) -> B[i,j] = sum of A[i],A[i+1],...,A[j]
    else -> B[i,j] = 0
}

(我认为)恰好与:

for i_{1,n}
{
    for j_{1,n}
    {
        B[i,j] = 0
        if (j > i)
        {
            for k_{i,j}
                B[i,j] += A[k];
        }
    }
}

这将使它成为一个三次复杂度算法。第三个循环在k上执行0次，然后执行1次，然后执行2次，然后执行3次，以此类推，直到执行n次。它的上界仍然是n。然后我们有两个循环与n迭代，所以我们的上限复杂度是n*n*n或O(n^3)。