c++ - 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) 效率吗？

score 3 · Accepted Answer

除极少数情况外，代码的复杂度为 O(1)。

这个想法是，当您（程序员）想要使用堆栈时，您会初始化堆栈以“几乎”一直有足够的空间。然后 Resize 永远不会被调用，或者至少很少被调用。

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

1 回答 1