单调栈算法：平均时间复杂度是θ(n)还是O(n)？

首先明确两个复杂度符号的核心区别：

• O(n)：仅描述时间复杂度的上界，表示算法运行时间不会超过线性时间，但无法说明下界情况。
• θ(n)：描述时间复杂度的紧界，同时确定了上界和下界，意味着算法运行时间恰好与输入规模n呈线性关系，既不会比线性时间更快，也不会更慢。

针对你提到的单调栈算法：
每个元素只会经历一次入栈和一次出栈操作，总操作次数严格与n呈线性关系（最多2n次操作）。无论是最优、最坏还是平均情况，总操作数的上界和下界都是线性的：

• 平均情况下，每个元素的操作次数是常数级，总时间复杂度的上下界都为线性，因此用*θ(n)*表述是更精确、严谨的选择。
• 虽然O(n)的表述本身没错，但它只给出了上界，无法体现算法在平均情况下不会比线性时间更优的特性，精度不如θ(n)。

内容的提问来源于stack exchange，提问作者user29898