循环内含if语句的代码最坏时间复杂度分析疑问

我分析下面这段代码的最坏时间复杂度时认为是O(n²)，但教授认为是O(n)，理由是每个元素最多执行两次操作（一次push和一次pop）。我有两个疑问：

1. 因为是if分支，每次只会走一个分支，怎么会同时包含push和pop操作？
2. 既然是最坏情况，为什么不能假设先入栈n-1个元素，最后一次迭代时遍历整个栈执行弹出操作，从而导致时间复杂度为O(n²)？

void foo (int n){
    Stack<int> stack = new Stack();

    i = 0;

    while (i < n) {
        int key = random int from 1 to n
        
        if (key is odd) 
            stack.push(key);
        else {
            j = 0;

            while (j < key and !stack.isEmpty()){
                stack.pop();
                j = j + 1;
            }
        }

        i = i + 1;
    }
}

疑问1解答 #

教授的说法不是指单次外层循环迭代里同时执行push和pop，而是指整个程序运行过程中，每个被push进栈的元素，最多只会被执行一次pop操作。

比如：某次外层循环生成奇数key，执行push把元素入栈；之后某次外层循环生成偶数key，进入else分支后，这个元素可能被pop出来。一旦被pop，这个元素就再也不会被任何操作处理了。

整个程序中，push操作的总次数最多是n（外层循环最多跑n次，每次最多push一次）；而pop操作的总次数绝对不会超过push的总次数（因为只有被push过的元素才能被pop），所以pop总次数最多也是n。两者加起来总操作数是O(n)，这就是教授结论的依据。

疑问2解答 #

你假设的场景，总操作数其实还是线性的，达不到O(n²)的量级：

• 前n-1次外层循环执行push，共n-1次操作；
• 最后一次外层循环执行n-1次pop，共n-1次操作；
• 总操作数是(n-1)+(n-1)=2n-2，这属于O(n)的范畴。

O(n²)要求总操作数是n×n的量级（比如每次外层循环都要遍历整个栈，且栈的大小每次都接近n），但在这段代码里，每个元素只会被pop一次，所有pop操作的总次数不可能超过push的总次数，而push最多n次，所以总操作数永远是线性的，不可能达到平方级。

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