-1

わかりましたので、次のとおりです。

二重リンク リストを使用し、その中のオブジェクトを並べ替えたいと考えています。オブジェクトは別のクラスです。奇妙なことに、自分で作成した二重連結リストを使用すると、要素をリストに追加した瞬間に要素を並べ替えます。これは挿入ソートのようなもので、効率は n^2 です。

しかし、これは、すべての要素をリストに追加してから sort() を呼び出す std::list 順序付けを使用するよりもはるかに高速です。そして、私は本当に理由がわかりません....

詳細については、現在、〜 500 個の要素を並べ替えています。

リストに何か問題がありますか?

編集：いくつかのコード

std::list のコード

for every object:
    list.push_back(object);
list.sort();

私のリスト：

struct node{
    someObject* data;
    float depth;
    node* prev;
    node* next;
    node(someObject* o){
        data = o;
        prev = NULL;
        next = NULL;
        depth = depthFunc(o);
    }
    float depthFunc(someObject* o);
};
struct myList{
    node* head;
    node* tail;
    void insertAfter(node* toAdd, node* n);
    void insertBefore(node* toAdd, node* n);
    void addNode(someObject* o){
        node* n = new node(o);
        if (head == NULL) {
            head = n;
            tail = n;
        } else {
            node* temp = head;
            while(temp != NULL && temp->depth < n->depth){
                temp = temp->next;
            }
            if (temp != NULL) insertBefore(n, temp);
            else insertAfter(n, tail);
        }
    }
};
4

1 に答える 1

2

手書きの並べ替え関数のN^2時間の複雑さは O( ) です。各要素が挿入され (回を呼び出します)、挿入ポイントを見つける操作addNode nが必要です(を与える)。nn * n = n^2

std::list<T>::sort()n lg nO( ) よりもはるかに高速なO( ) の複雑さが必要ですN^2。(lg nよりもはるかにゆっくりと成長しますn)

手書きの sort は、挿入 sortのバリアントです。

ほとんどの入力では、 and の代わりに and を使用すると、より高速な結果が得られることに注意std::vectorしstd::sortてstd::listくださいstd::list::sort。

あなたの質問が「手書き版の方が速いのはなぜですか?」という質問であれば、それはあなたの意見次第です。挿入ソートはO(n)、一部の入力に対して行うことができます。（実装では、要素が逆の順序で挿入されたときに発生します）

于 2013-04-22T23:21:20.210 に答える