python - a.insert(0，x)是o(n)函数吗？ a.append是O(1)函数吗？ python

我试图将数组中的偶数移到数组的前面，将奇数移到数组的后面。问题要求在线性算法中执行此操作并就地执行此操作。

我想出了这个：

 def sort(a):
    for i in range(0,len(a)-1):
        if a[i]%2==0:
            a.insert(0,a.pop(i))
    return a

问题是，有人告诉我，从技术上讲，a.insert是o（n）函数，因此从技术上讲，这将被视为非线性算法（当包含函数的for i in range部分时）。由于提出这个问题的论坛已有两个月的历史，因此我无法要求您做出任何解释。

基本上，我相信他说的是“技术上”，因为既然它是在前面插入的，所以它不会检查数组中另外N个元素，因此使它在O（n）而不是O（n ^ 2）上用于实际目的。这是正确的评估吗？

另外，论坛上的某人使用a.append修改了上述内容，并将其更改为寻找奇数。没有人回答，所以我想知道，a.append是否不是o（n）函数，因为它将其移至末尾？是o（1）吗？

感谢您的解释和澄清！

最佳答案

列表第0个索引处的insert需要移动其他所有元素，使其沿其成为O（N）运算。但是，如果使用deque，则此操作为O（1）。

append是摊销的O（1）运算，因为它只需要将项目添加到列表的末尾，并且不进行任何移位。有时列表需要增长，因此它并不总是O（1）操作。

关于python - a.insert(0，x)是o(n)函数吗？ a.append是O(1)函数吗？ python ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11336978/