c - 寻找下一个更大元素线性时间的渐近复杂度如何？

Question

我正在阅读 an algorithm to get the Next Greater Element for each element of an array .

该网站声称他们的代码在 O(n) 时间内运行，但我无法理解它。

从左到右完整遍历数组本身的成本为 O(n)，在此基础上，当我们遍历列表时，每个索引处可以有多个 push/pop 操作。

虽然 push/pop 操作需要常数时间，如果它们平均每个索引元素调用 m 次，我们将有 O(m) 作为每个索引处的 push/pop 操作的成本，导致 O(mn) 作为总成本，现在因为 push/pop 操作的总数应该大约(或可能恰好)等于 n，我们可以说 mn 大约(或可能恰好)等于 n，这意味着 m 是一个常数.

我的理由对吗？

我对自己的推理仍然不太清楚，除了验证/否定我的理由之外，有人可以提供更好的解释吗？

Answer 1

为方便起见复制在这里的伪代码:

1. Push the first element to stack.
   
2. Pick rest of the elements one by one and follow following steps in loop.
   
   1. Mark the current element as next.
      
   2. If stack is not empty, then pop an element from stack and compare it with next.
      
   3. If next is greater than the popped element, then next is the next greater element for the popped element.
      
   4. Keep popping from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements
      
   5. If next is smaller than the popped element, then push the popped element back.
      
   6. Push next onto the stack [this step is missing from the pseudo-code]
3. After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.

外层循环运行 O(n) 次。

显然，除了为未被推回的弹出元素所做的工作(步骤 #4，减去它处理的最后一个元素)之外，循环迭代的其余部分是常数时间。

因此，任何不断弹出并推回堆栈的元素都将包含在每次弹出和推回的迭代的恒定时间内。

剩下的就是元素被弹出而不是被推回的时间，但显然这对每个元素只能发生一次，因此这总共占 O(n) 运行时间.

因为我们从不重复堆栈中的项目(我们从数组中压入每个元素一次，然后我们只在弹出后再次压入)所以不能超过 n 个元素堆栈，所以最后一步最多花费 O(n) 时间。

因此总运行时间是O(n + n + n) = O(n)。

---

另一种推理方式:

我们在每次循环迭代期间最多执行 2 次推送操作(有 n 次)。

因此最多有 2n 次推送操作，因此也最多有 2n 次弹出操作(我们不能弹出未推送的元素)。

我们在每个 push/pop 操作中做恒定量的工作，并且我们在每个循环迭代中额外做恒定量的工作(忽略每个 push/pop 操作完成的工作)，因此总运行时间是 O (n + 4n) = O(n)。