我想我至少开始理解大哦符号背后的理论，即它是一种衡量函数速度增长速度的方法。换句话说，大 O 量化了算法的效率。但它的实现是另一回事。
例如，在最好的情况下，push 和 pull 操作将是 O(1)，因为从堆栈中删除或添加到堆栈所需的步骤数将是固定的。不管值是多少，过程都是一样的。
我试图设想一系列事件（例如 push 和 pop）如何将性能从 O(1) 降低到 O(n^2)。如果我有一个 n/2 容量的数组，n 个 push 和 pop 操作，以及一个在满或半满时容量加倍或减半的动态数组，这些操作发生的顺序怎么可能影响速度哪个程序完成？由于 push 和 pop 在堆栈的顶部元素上工作，我无法看到效率如何从常数变为 O(n^2)。
提前致谢。
您假设动态数组非常智能地执行其调整大小操作。但是，如果不是这种情况，您最终可能会得到 O(n^2) 运行时：假设数组在满时不会使其大小加倍，而只是将大小调整为 size+1。另外，假设它从大小 1 开始。您将在 O(1) 中插入第一个元素。插入第二个元素时，需要将数组大小调整为 2，要求它复制前一个值。插入元素 k 时，它当前的大小为 k-1，需要调整大小为 k，导致需要复制 k-1 个元素，依此类推。
因此，对于插入 n 个元素，您最终会复制数组 n-1 次：O(n) 调整大小。复制操作也线性依赖于 n，因为插入的元素越多，需要复制的越多：每次调整大小 O(n) 份。这导致 O(n*n) = O(n^2) 作为其运行时复杂度。
如果我将堆栈实现为（比如说）一个链表，那么推送和弹出将始终是恒定时间（即 O(1)）。
我不会为堆栈选择动态数组实现，除非运行时对我来说不是问题，我碰巧有一个已构建好的动态数组可供使用，而且我没有更有效的堆栈实现方便。但是，如果我确实使用了一个在它变满或半空时向上或向下调整大小的数组，它的运行时间将是 O(1) 而推送和弹出的数量足够低，不会触发调整大小和 O(n ) 当有调整大小时（因此总体 O(n)）。
我想不出用作堆栈的动态数组可以提供与 O(n^2) 一样糟糕的性能的情况，除非其实现中存在错误。