用递归反转堆栈的时间复杂度

Question

我试图找到以下代码的时间复杂度。

int insert_at_bottom(int x, stack st) {
if(st is empty) {
    st.push(x)
}
else {
    int a = st.top()
    st.pop()
    insert_at_bottom(x)
    st.push(a)
}
}
void reverse(stack st) {
    if(st is not empty) {
        int st = st.top()
        st.pop()
        reverse(st)
        insert_at_bottom(x, st)
    }
}
// driver function
int[] reverseStack(int[] st) {
    reverse(st)
    return st
}

对于堆栈顶部的每个元素，我们弹出整个堆栈，将顶部元素放在底部，这需要 O(n) 操作。而这些O(n)的操作是针对栈中的每一个元素进行的，所以时间复杂度应该是O(n^2).

但是，我想从数学上求出时间复杂度。我试图找到递推关系，我得到了 T(n)=2T(n-1)+1。这可能是错误的，因为第二个函数调用的时间复杂度不应视为 T(n-1)。

Answer 1

你的论点大体上是正确的。如果底部插入需要O(n)时间，那么反向函数需要O(n²) 时间，因为它对每个元素在堆栈上执行线性时间操作。

reverse() 的递归关系看起来有点不同。在每个步骤中，您要做三件事：

在 n-1
一个O(n)次操作(insert_at_bottom())
一些恒定时间的东西

因此，您可以将这些加在一起。所以我认为它可以写成：

T(n) = T(n-1) + n + c，其中 c 是一个常数。

你会发现，由于递归，T(n-1) = T(n-2) + n-1 + c。因此，如果在 n > 0 下以这种方式继续扩展整个系列，您将获得：

T(n) = 1 + ... + n-1 + n + nc

因为1 + 2 + ... + n) = n(n + 1)/2（见this），我们得到

T(n) = n(n+1)/2 + nc = n²/2 + n/2 + nc = O (n²)。 □

insert_at_bottom()的O(n)次，你可以用类似的方式展示。

用递归反转堆栈的时间复杂度

Time complexity of reversing a stack with recursion

recursion

time-complexity