arrays - 理由 - マージソート 英語




なぜ、mergesortの空間の複雑さはリンクリストのO(log(n))ですか? (2)

配列上のMergesortは空間の複雑さがO(n)であり、リンクされたリスト上のmergesortは空間の複雑さがO(log(n))であり、 ここで文書化されている

私は2つのサブアレイをマージするときに補助記憶装置が必要なので、配列の場合を理解していると思います。 しかし、リンクリストのマージソートでは、2つのサブリンクリストをマージするだけでは問題ありませんか? 私はこれが新しい頭部を作るために空間の複雑さO(1)を持つと思う。

マージ場所(補助記憶域なし):

public Node merge(Node a, Node b) {
    Node dummyHead, curr; dummyHead = new Node(); curr = dummyHead;
    while(a !=null && b!= null) {
        if(a.info <= b.info) { curr.next = a; a = a.next; }
        else { curr.next = b; b = b.next; }
        curr = curr.next;
    }
    curr.next = (a == null) ? b : a;
    return dummyHead.next;
}

説明は素晴らしいでしょう。


Mergesortは再帰的アルゴリズムです。 各再帰的ステップは、スタックに別のフレームを置きます。 64個のアイテムをソートすると、32個のアイテムよりも再帰的なステップが1つ多くなり、実際にはスペース要件がO(log(n))であると言われるスタックのサイズになります。


mergesortアルゴリズムは再帰的であるため、配列の場合とリンクされたリストの場合の両方で、O(log n)のスタック空間が必要です。 しかし、配列の場合も、スタックに必要なO(log n)スペースを支配する追加のO(n)スペースが割り当てられます。 したがって、配列のバージョンはO(n)であり、リンクされたリストのバージョンはO(log n)です。





linked-list