C++函数的效率

Question

有人告诉我，以下代码的效率为O(1)：

void mystack::Pop_element()
{
    assert ( nelem > 0 );

    nelem--;

    if ( nelem < reserved / 4 ){

        Resize ( reserved / 2 );

    }
}

但我真的不明白为什么，因为Resize有效率O(n) (这是事实，我们不应该知道Resize内部的代码)。那么，整个代码不也应该具有O(n)效率吗？

Answer 1

该代码的复杂性是O(1)，除非在非常罕见的情况下。

其思想是，当您(程序员)想要使用堆栈，您初始化堆栈，以拥有足够的空间“几乎”任何时候。然后调整大小永远不会被调用，或者至少很少被调用。

在特殊情况下是迂腐的，可以将其称为摊销常数时间，因为时间复杂性是不变的，除非在特殊情况下。

另见：Constant Amortized Time