为什么python的list.append()方法的时间复杂度是O(1)？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/33044883/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Why is the time complexity of python's list.append() method O(1)?
提问by ohad edelstain
As seen in the documentation for TimeComplexity, Python's listtype is implemented is using an array.
正如TimeComplexity的文档中所见，Python 的list类型是使用数组实现的。
So if an array is being used and we do a few appends, eventually you will have to reallocate space and copy all the information to the new space.
After all that, how can it be O(1) worst case ?
因此，如果正在使用数组并且我们进行了一些附加操作，最终您将不得不重新分配空间并将所有信息复制到新空间。
毕竟，它怎么可能是 O(1) 最坏的情况？
采纳答案by Jacob Ritchie
If you look at the footnote in the document you linked, you can see that they include a caveat:
如果您查看链接文档中的脚注，您会发现其中包含一个警告：
These operations rely on the "Amortized" part of "Amortized Worst Case". Individual actions may take surprisingly long, depending on the history of the container.
这些操作依赖于“摊销的最坏情况”的“摊销”部分。根据容器的历史记录，单个操作可能需要非常长的时间。
Using amortized analysis, even if we have to occasionally perform expensive operations, we can get a lower bound on the 'average' cost of operations when you consider them as a sequence, instead of individually.
使用摊销分析，即使我们必须偶尔执行昂贵的操作，当您将它们视为一个序列而不是单独考虑时，我们可以获得操作“平均”成本的下限。
So, any individual operation could be very expensive - O(n) or O(n^2) or something even bigger - but since we know these operations are rare, we guarantee that a sequence of O(n) operations can be done in O(n) time.
因此，任何单独的操作都可能非常昂贵——O(n) 或 O(n^2) 或更大的东西——但由于我们知道这些操作很少见，我们保证一系列 O(n) 操作可以在准时。
回答by rlbond
It's amortized O(1), not O(1).
它的摊销时间为 O(1)，而不是 O(1)。
Let's say the list reserved size is 8 elements and it doubles in size when space runs out. You want to push 50 elements.
假设列表保留大小是 8 个元素，当空间用完时它的大小加倍。您想推送 50 个元素。
The first 8 elements push in O(1). The nineth triggers reallocation and 8 copies, followed by an O(1) push. The next 7 push in O(1). The seventeenth triggers reallocation and 16 copies, followed by an O(1) push. The next 15 push in O(1). The thirty-third triggers reallocation and 32 copies, followed by an O(1) push. The next 17 push in O(1).
前 8 个元素推入 O(1)。第 9 个触发重新分配和 8 个副本，然后是 O(1) 推送。接下来的 7 次推入 O(1)。第十七次触发重新分配和 16 个副本，然后是 O(1) 推送。接下来的 15 次推入 O(1)。第 33 次触发重新分配和 32 个副本，然后是 O(1) 推送。接下来的 17 次推入 O(1)。
So all of the pushes have O(1) complexity, we had 56 copies at O(1), and 3 reallocations at O(n), with n = 8, 16, and 32. Note that this is a geometric series and asymptotically equals O(n) with n = the final size of the list. That means the whole operation of pushing n objects onto the list is O(n). If we amortizethat per element, it's O(n)/n = O(1).
所以所有的推送都有 O(1) 的复杂度，我们在 O(1) 处有 56 个副本，在 O(n) 处有 3 次重新分配，n = 8、16 和 32。请注意，这是一个几何级数并且渐近等于 O(n)，其中 n = 列表的最终大小。这意味着将 n 个对象推入列表的整个操作是 O(n)。如果我们按元素摊销，则为 O(n)/n = O(1)。
回答by Isaac Chou
This is very easy.
这很容易。
We can calculate this by accumulating the total time of appending n elements into an arraylist and divide it by n.
我们可以通过累积将 n 个元素添加到数组列表中的总时间并将其除以 n 来计算。
Firstly, we need to relocate log(n) times, and every relocation is doubled by 2.So we have a proportional series whose ratio is 2, and the length is log(n).
首先，我们需要重定位log(n)次，每次重定位加2倍。所以我们有一个比例序列，比例为2，长度为log(n)。
The sum of a proportional series is a(1-r^n)/(1-r) So the total time of relocation is (1-n)/(1-2)=n The time complexity would be n/n=1.
一个比例序列的总和是 a(1-r^n)/(1-r) 所以重定位的总时间是 (1-n)/(1-2)=n 时间复杂度是 n/n= 1.
