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

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

对我来说看起来是 O(n^2) 。我猜测已经排序的堆栈具有最坏情况的性能。s.push给定特定大小的已排序堆栈，我计算了执行的次数。

Stack of size 1. backpushes: 0
Stack of size 2. backpushes: 1
Stack of size 3. backpushes: 3
Stack of size 4. backpushes: 6
Stack of size 5. backpushes: 10
Stack of size 6. backpushes: 15
Stack of size 7. backpushes: 21
Stack of size 8. backpushes: 28
Stack of size 9. backpushes: 36

0,1,3,6,10是三角形数的序列。大小为 N 的排序堆栈需要 (N^2 + N)/2 次反推。这使得它的复杂度为 O(N^2)。