大哦符号-推送和弹出
大哦符号-推送和弹出
提问于 2013-01-23 08:26:31
我想我至少开始理解大Oh符号背后的理论了，也就是说，它是一种测量函数速度增长速度的方法。换句话说，大O量化了算法的效率。但它的实现是另一回事。
例如，在最好的情况下，推送和拉取操作将是O(1)，因为从堆栈中删除或添加到堆栈所需的步骤数将是固定的。不管值是多少，过程都是一样的。
我正在尝试想象一系列事件(如push和pop )如何将性能从O(1)降低到O(n^2)。如果我有一个n/2容量的数组，n个推送和弹出操作，以及一个在满或半满时使其容量加倍或减半的动态数组，那么这些操作发生的顺序如何可能影响程序完成的速度？因为push和pop在堆栈的顶部元素上工作，所以我看不出效率是如何从一个常量变为O(n^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提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14470485
复制相关文章
相似问题
腾讯云开发者
