performance - 使用另一个堆栈对堆栈进行排序

Question

我想知道这个算法的时间复杂度，该算法用于使用另一个堆栈对堆栈进行排序。我认为它是 O(N^2)，但显然它看起来不止于此。

public static Stack<Integer> sort(Stack<Integer> s) {
    Stack<Integer> r = new Stack<Integer>();

    while(!s.isEmpty()) {
        int tmp = s.pop();
        while(!r.isEmpty() && r.peek() > tmp) {
            s.push(r.pop());
        }
        r.push(tmp);
    }
    return r;
}

Answer 1

如果排序堆栈 [x_2, .., x_n](堆栈向右增长)需要 t(n-1) 时间，排序堆栈 [x_1 , .., x_n] 时间将执行以下操作

1. 对 s 的子堆栈 [x_2, .., x_n] 进行排序
2. 将 x_1 弹出到 tmp
3. 最多将n-1个元素从r转移到s
4. 将x_1推送到r
5. 再次处理步骤 3 中传输的元素，但它们的顺序使得内部 while 循环永远不会运行。

因此在[x_1, .., x_n] 上运行算法最多需要t(n-1) + O(n) 时间。这导致(对于一些常量 c)

t(n) <= O(n) + t(n-1) <= c * n + t(n-1)
t(n) <= c * n + c * (n - 1) + t(n-2) <= ... <= c * (1 + 2 + ... + n)
t(n) <= c * n(n + 1) / 2 

所以 t(n) 是 O(n^2)。