a.insert(0,x)是o(n)函数吗？是否支持O(1)功能？蟒蛇

Question

我试图将数组中的偶数移到前面,将奇数移到数组的后面.该问题要求在线性算法中执行此操作并在此处执行此操作.

我想出了这个:

 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)？

感谢您的解释和澄清!

Answer 1

insert在列表的第 0 个索引处需要移动每个其他元素，这使其成为 O(N) 操作。但是，如果您使用deque此操作，则此操作是 O(1)。

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

Answer 2

这是正确的 - 在Python标准列表的前面插入是O(n).Python列表实现为数组,因此在列表的前面插入一些内容需要将整个内容转移到一个位置.另一方面,附加不需要任何转移,因此摊销O(1).

但是请注意,该a.pop(i)是也为O(n)的操作,因为它需要在一个点被弹起项后移的一切.因此,简单地修改您的代码append()而不是insert()仍然不会导致线性算法.

线性时间算法不会使用pop(),而是会执行类似交换元素的操作,以便不必修改列表的其余部分.例如,考虑一下:

def even_to_front(a_list):
    next_even = 0
    for idx in xrange(len(a_list)):
        if not a_list[idx] % 2:
            # a_list[idx] is even, so swap it towards the front
            a_list[idx], a_list[next_even] = a_list[next_even], a_list[idx]
            next_even += 1