1

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

我想出了这个：

 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）吗？

感谢您的解释和澄清！

4

5 回答 5

7

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

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

于 2012-07-05T01:49:07.450 回答
5

这是正确的 - 在 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
于 2012-07-05T01:49:31.540 回答
2

这是在没有附加/插入或出列的情况下如何完成的

def sort(L):
    i, j = 0, len(L)-1
    while i<j:
        # point i to the next odd number from the start
        while i<j and not L[i]%2: i+=1
        # point j to the next even number from the end
        while i<j and L[j]%2: j-=1
        L[i],L[j] = L[j],L[i]
于 2012-07-05T02:38:04.617 回答
1

检查这个复杂度表

  • 插入 - O(n)
  • 追加 - O(1)（列表过度分配）
于 2012-07-05T01:49:22.410 回答
0

每次pop从列表中获取元素时，都必须复制列表的尾随部分以将其移动到一个索引上，以填补被移除元素留下的空洞。这在弹出元素和列表尾部之间的距离是线性的。

每次insert将元素放入列表时，都必须复制列表的尾随部分以将其移动到一个索引上以创建插入新元素的位置。这在插入元素的位置与列表尾部之间的距离是线性的。

如果使用collections.deque，则可以及时追加和弹出到前面和后面O(1)。但是，从中间删除一个元素仍然是线性的（我认为您必须自己编写）。

于 2012-07-05T01:51:12.067 回答