1

二重にリンクされたリストから要素を削除する時間の複雑さは O(1) であり、明白で明確に見えますが、削除する要素を受信せず、要素によってラップされている要素を受け取っていない場合はどうなりますか?

たとえば、クラス Element を定義して文字列をラップする場合 (次および前の要素を指すポインターを提供するため)、メソッドがその要素を文字列ではなく入力として受け取る場合、O(1) で削除を実行できます。

remove メソッドが文字列を受け取った場合、対応する要素を見つけるためにリストを検索する必要がありますね。したがって、この場合の時間計算量は O(1) ではなく O(n) になります。

  class Element{
    String content;
    Element next;
    Element previous;
  }

  class LinkedList{
    ...
    public remove(String s){
        //it has to first find the element corresponding to this String !
    }
  }
4

2 に答える 2

0

このリンクされたリスト (循環、二重にリンクされたリスト、ノードとオブジェクトの関係を管理する方法は? ) は、リストに追加されるオブジェクトにプロパティを挿入する非常に疑わしい方法を使用します。オブジェクトを検索せずに O(1) を削除しますが、リストにプリミティブ型を追加すると、プロパティ名が競合し、パフォーマンスが低下するリスクがあります (プロパティが追加されるとボックス化されます)。

于 2014-03-02T14:09:05.523 に答える