a.insert(0，x)是o(n)函数吗? a.append是O(1)函数吗? Python [英] Is a.insert(0,x) an o(n) function? Is a.append an O(1) function? Python

问题描述

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

I am trying to move even numbers in an array to the front and odd numbers to the back of the array. The problem asks to do this in a Linear Algorithm and do this In Place.

我想到了这个

 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部分时).由于提出这个问题的论坛已有两个月的历史了，所以我无法要求任何解释.

The issue is that, someone told me that technically, a.insert is an o(n) function so technically this would be considered a non-linear algorithm (when including the for i in range part of the function). Since the forum that asked this question is a couple months old, I couldn't ask for an explanation.

基本上，我相信他说的是技术上"，因为因为它是在前面插入的，所以它不会检查数组中另外N个元素，因此使它在O(n)而不是O(n ^ 2).这是正确的评估吗?

Basically I believe he said "Technically" because since this inserts it at the front, it does not check another N number of elements in the array, therefore making it run for practical purposes at O(n) and not O(n^2). Is this a correct assessment?

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

Also, someone on the forum used a.append to modify the above and changed it to look for odd numbers. No one replied so I was wondering, is a.append not an o(n) function since it moves it to the end? Is it o(1)?

感谢您的解释和澄清！

推荐答案

insert在列表的第0个索引处需要移位其他所有元素，使其沿其进行O(N)操作.但是，如果您使用 deque ，则此操作为O(1 ).

insert at the 0th index of a list requires shifting every other element along which makes it an O(N) operation. However, if you use a deque this operation is O(1).

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

append is an amortized O(1) operation since it simply requires adding the item on to the end of the list and no shifting is done. Sometimes the list needs to grow so it is not always an O(1) operation.

这篇关于a.insert(0，x)是o(n)函数吗? a.append是O(1)函数吗? Python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！