algorithm - 对子数组求和将如何影响嵌套 for 循环中的时间复杂度？

Question

试图计算一些简单代码的时间复杂度，但我不知道如何在对子数组求和时计算时间复杂度。代码如下:

for i=1 to n {
   for j = i+1 to n {
       s = sum(A[i...j])
       B[i,j]=s
}}

所以我知道嵌套的 for 循环不可避免地给我们一个 O(n^2)，我相信求和到子数组的函数也是 O(n^2)。但是，我认为整个算法的时间复杂度是 O(n^3)。我如何获得这些信息？谢谢!

Answer 1

我喜欢将 for 循环视为求和。因此，步数(写成一个函数，T(n))是:

T(n) = \sum_{i=1}^n numStepsInInnerForLoop

在这里，我使用了一些用伪 MathJax 编写的东西，并将外部 for 循环编写为从 i=1 到 n 的总和内部 for 循环中的步骤(从 i+1 到 n 的步骤)。您可以将其类比地认为是将内部 for 循环中的步骤数相加，从 i=1 到 n。替换为 numStepsInInnerForLoop 结果:

T(n) = \sum_{i=1}^n [\sum_{j=i+1}^n numStepsOfSumFunction]

这个函数现在表示两个 for 循环都被充实为总和的步骤数。假设 s = sum(A[i...j]) 需要 j-i+1 步并且 B[i,j]=s 只需一步，我们可以将 numStepsOfSumFunction 替换为这些更有用的参数，现在等式变为:

T(n) = \sum_{i=1}^n [\sum_{j=i+1}^n (j-i+1 + 1)]

当您解决这些求和时(使用您在 this summation tutorial page 上看到的那种公式)，您将获得 T(n) 的三次函数，它对应于 O(n^ 3)。