0

我想在 python 中编写一个 list-lie 类，当添加数字时它会自动排序。这是为了好玩，而不是为了上课：p 我想知道的是最有效的方法是什么。我应该做这样的事情吗？：

class SortedList:
    def __init__(self, data):
        self.data = list(data)

    def add(self, num):
        self.data.append(num)
        self.data.sort()

有没有更好的方法来做到这一点？

4

2 回答 2

2

-编辑- sort()是 O(n log n)。在每个添加的数字之后通过排序将 n 个数字添加到列表中将是 O(n^2 log n)（但实际上这可能比 O(n^2) 算法更快，具体取决于排序的优化） .

更好的 O 实现是花费 O(n) 时间来搜索插入位置，并花费 O(n) 时间将新数字添加到列表中（总时间仍然 O(n)）。将 n 个数字添加到列表中将是 O(n^2)。代码如下：

def addFaster(self, num):
    index = 0
    if(len(self.data) == 0):
        self.data = [num]
    else:
        for i in range(0, len(self.data)):
        if(self.data[i] >= num):
            self.data.insert(i, num)
            return
        self.data.append(num)

我们可以通过在 O(log n) 时间内对正确索引进行二进制搜索来做得更好。向列表中添加一个新数字是 O(n)。由于整个操作是（比以前更好）O(n)，将 n 个数字添加到列表中是 O(n^2)，具有较低的常数。（不包括代码）

extend()但是，如果您要在大组中添加新数字，如果您一次将它们全部添加（使用）然后排序，它将大大加快算法速度。然后，添加 n 个数字将在 O(n log n) 时间内完成（与排序相同）。

见http://wiki.python.org/moin/TimeComplexity

于 2012-09-14T05:15:29.973 回答
1

您指定您希望将其实现为列表；您是否考虑过将数据结构视为堆？可能更适合您正在尝试做的事情。

见heapq。

于 2012-09-14T05:34:34.090 回答