大哦符号-推送和弹出
我想我至少开始理解大Oh符号背后的理论了，也就是说，它是一种测量函数速度增长速度的方法。换句话说，大O量化了算法的效率。但它的实现是另一回事。
例如，在最好的情况下，推送和拉取操作将是O(1)，因为从堆栈中删除或添加到堆栈所需的步骤数将是固定的。不管值是多少，过程都是一样的。
我正在尝试想象一系列事件(如push和pop )如何将性能从O(1)降低到O(n^2)。如果我有一个n/2容量的数组，n个推送和弹出操作，以及一个在满或半满时使其容量加倍或减半的动态数组，那么这些操作发生的顺序如何可能影响程序完成的速度？因为push和pop在堆栈的顶部元素上工作，所以我看不出效率是如何从一个常量变为O(n^2)的。
提前谢谢。
回答 2
Stack Overflow用户
发布于 2013-01-23 23:43:28
您假设动态数组非常智能地执行其大小调整操作。然而，如果不是这样，你可能会以O(n^2)运行时结束:假设数组在满的时候并没有加倍它的大小，而只是简单地将大小调整为size+1。当插入第二个元素时，需要将数组的大小调整为2，这要求它复制前一个值。当插入元素k时，它当前的大小为k-1，并且需要将大小调整为k，从而导致需要复制k-1个元素，依此类推。
因此，要插入n个元素，您需要将数组复制n-1次: O(n)大小。复制操作也线性依赖于n，因为插入的元素越多，需要复制的就越多:每次调整大小都需要复制O(n)个副本。这导致O(n*n) = O(n^2)作为其运行时复杂性。
Stack Overflow用户
发布于 2013-01-23 08:46:33
如果我将一个堆栈实现为(比方说)一个链表，那么pushes和pops将总是恒定的时间(即O(1))。
我不会为堆栈选择动态数组实现，除非运行时对我来说不是问题，我碰巧有一个现成的动态数组可用，而且我手头没有更有效的堆栈实现。然而，如果我确实使用了一个数组，当它变成满的或半空的时候，它的运行时间将是O(1)，而推和弹出的数量足够低，不足以触发调整大小，而当有调整大小时，它的运行时将是O(n) (因此总体为O(n))。
我想不出有哪种情况下，用作堆栈的动态数组可以提供像O(n^2)这样糟糕的性能，除非它的实现中存在错误。
https://stackoverflow.com/questions/14470485
复制相似问题
腾讯云开发者
