python - 收集雨水的时间复杂度

Question

我一直在研究 problem 的不同算法在 Leetcode 上以 approach 1 开头.如果数组值是墙的高度，则该问题需要计算总水域面积(列宽 = 1)。

第一种方法找到每列左侧和右侧最大墙高的最小高度，如果列高度小于最小值，则将水添加到给定列的顶部。取最小值是因为这是收集到的水可以达到的最高值。要计算每边的最大值，需要对左侧和右侧进行 n-1 遍历。

我用 Python 编写代码，但这里是根据 Leetcode 上给出的解决方案用 C++ 编写的代码.问题不在于理解 C++，而是在代码之后解释的数学。

int trap(vector<int>& height)
{
    int ans = 0;
    int size = height.size();
    for (int i = 1; i < size - 1; i++) {
        int max_left = 0, max_right = 0;
        for (int j = i; j >= 0; j--) { //Search the left part for max bar size
            max_left = max(max_left, height[j]);
        }
        for (int j = i; j < size; j++) { //Search the right part for max bar size
            max_right = max(max_right, height[j]);
        }
        ans += min(max_left, max_right) - height[i];
    }
    return ans;
}

我不明白他们是如何达到时间复杂度 O(n^2) 的。我得到了 O(n^3)。

Index | Comparisons/Traversals
-------------------------------
  1   |            n
  2   |            n
  3   |            n
  4   |            n
  .   |            .
  .   |            .
  .   |            .
 n-1  |            n

此处执行的总操作为: n + 2n + 3n + 4n + n(n-1) + n^2

现在用等差级数公式 Sum = n * (a_1 + a_n)/2 得到here并粘贴在下面

上面的总和最终会是:

Sum = n * [n + n(n-1)]/ 2 = n * [n + n^2- n)]/ 2 = (n^3)/2

这将给出 O(n^3)。

我的推理有什么问题？它似乎是 O(n^2) 作为 GeeksForGeeks也指出了这一点。

Answer 1

问题出在这里:

The total operations performed here would be: n + 2n + 3n + 4n + n(n-1) + n^2

但是你的表的每一行只是 n，而不是 n, 2n, …, n^2。

快速浏览一下，很明显您也正确地填写了表格:内部循环有 O(n) 个恒定时间步。

您所做的所有其他数学运算都是正确的，但无关紧要。总结 n 份 n，你只是多个 n * n，当然是 n^2 ，不是 O(n^3)。