algorithm - 为什么这个算法的空间复杂度是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

Answer 1

第一行说明了一切:

Create arrays S and T each of size n.

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

一般来说，算法的空间复杂度取决于使用的局部变量的数量以及它们的大小。数组、映射、集合、树等占用的空间与它们包含的元素数量成正比，因此如果您只使用固定数量的变量，如果它们最终存储多个变量，您仍然可以使用超过 O(1) 的空间元素。

希望这对您有所帮助!