为什么这个算法的空间复杂度是O(n)？

Question

这是使用DP方法寻找最大连续子序列和的算法。该算法似乎相当不错，但提到它的空间复杂度为O(n)。为什么呢？

对我来说，这个算法的空间复杂度似乎是O(1)。

另外一个我想问的问题是，在没有使用任何递归的算法中，是否可能拥有除常数空间复杂度以外的其他复杂度？

Create arrays S and T each of size n.
    S[0] = A[0];
    T[0] = 0;
    max = S[0];
    max_start = 0, max_end = 0;

    For i going from 1 to n-1:
    // We know that S[i] = max { S[i-1] + A[i], A[i] .
         If ( S[i-1] > 0)
           S[i] = S[i-1] + A[i];
           T[i] = T[i-1];

         Else
           S[i] = A[i];
           T[i] = i;

         If ( S[i] > max)
           max_start = T[i];
           max_end = i;
           max = S[i];
    EndFor.

Output max_start and max_end

- bigbong

---

创建大小为n的数组S和T。通过创建两个大小为n的数组，您将使用O(n)额外空间。 - amit

顺便提一下，这里其实不需要额外的O(n)空间..Kadane算法只需要常数级的空间：http://marcodiiga.github.io/maximum-and-maximum-zero-sum-subarray-problems - Marco A.

Answer 1

首行就说了一切：

创建大小为n的数组S和T。

大小为n的数组需要Θ(n)的空间，所以您的算法自动使用Ω(n)的空间。查看算法的其余部分，可以看到只使用O(1)的其他变量，并且没有递归，因此总使用的空间是Θ(n)。

通常，算法的空间复杂度取决于使用的本地变量数量及其大小。数组、映射、集合、树等占用的空间与它们保存的元素数量成比例，因此如果您只使用常数个变量，则仍然可以使用多于O(1)的空间，如果它们最终存储多个元素。

希望这有所帮助！

- templatetypedef