求和 运行 时间分析

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 次迭代。 我的问题是如何做 if(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 次，然后执行两次，然后执行三次，依此类推，直到执行 n 次。它的上限仍然是n。然后我们还有两个循环 n 迭代，所以我们的上限复杂度是 n*n*n 或 O(n^3).