0

数字が追加されると自動的にソートされるリスト嘘クラスをPythonで書きたいと思います。これは楽しみのためであり、クラスのためではありません: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

-Edit- 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 に答える