5

这是使用 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
4

1 回答 1

7

第一行说明了一切：

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

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

通常，算法的空间复杂度取决于使用的局部变量的数量以及它们的大小。数组、映射、集合、树等占用的空间与它们所拥有的元素数量成正比，所以如果你只使用恒定数量的变量，如果它们最终存储多个变量，你仍然可以使用超过 O(1) 的空间元素。

希望这可以帮助！

于 2013-11-07T07:11:23.693 回答