8

次の操作の時間計算量はjava.util.TreeSetどれくらいですか？

  • first()
  • last()
  • lower()
  • higher()

これらは一定の時間であると思いますが、APIは保証しません。

4

5 に答える 5

12

O(logN)実は、これらの操作はすべて一般的な実装になると思いました。

  • first()TreeSetの実装でlast()あるためO(1)には、ツリーの左端と右端のリーフノードへのポインタをそれぞれ維持する必要があります。これらを維持すると、すべての挿入に一定のコストが追加され、少なくともすべての削除に一定のコストが追加されます。実際には、実装はおそらくその場で左/右端のノードを見つけるでしょう...これはO(logN)操作です。

  • lower()およびメソッドは、higher()と同じ作業を行う必要getがあるため、ですO(logN)。

もちろん、ソースコードを自分でチェックして、実際に何が起こっているかを確認することもできます。（他の人が行ったように：以下を参照してください。）

于 2011-03-07T00:59:00.430 に答える
2

デフォルトでTreeSetによって使用されるTreeMapのImplentation（sun jdk 1.6.0_23）に基づくと、first（）とlast（）の両方がO（log n）であり、O（1）ではないように見えます。

 /**
 * Returns the first Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}

/**
 * Returns the last Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}
于 2012-08-11T06:58:49.843 に答える
1

私は実際にソースコードを調べました。http： //developer.classpath.org/doc/java/util/TreeSet-source.htmlで、first（）がmaps.firstKey（）を呼び出し、次に http：//developer.classpathを呼び出します。 org / doc / java / util / TreeMap-source.html

393: public K firstKey()
394: (
395: if (root == nil)
396: throw new NoSuchElementException();
397: return firstNode().key;
398: )

そしてfirstNode（）では、whileループを実行して左端まで移動します

952: final Node<K, V> firstNode()
953: (
954: // Exploit fact that nil.left == nil.
955: Node node = root;
956: while (node.left != nil)
957: node = node.left;
958: return node;
959: )
于 2015-01-16T20:57:03.283 に答える
-2

これらはトライの標準モデルに基づいているため、APIは保証しません。最良のケースはO（1）で、平均的なケースはO（log n）で、最悪のケースはO（n）です。

ドキュメントから：

この実装は、基本操作（追加、削除、および含む）に保証されたlog（n）時間コストを提供します。

これらはあなたが求めた関数ではありませんが、JavaがTreeSetをどのようにトラバースするかを考えてください。

于 2011-03-07T00:58:02.413 に答える
-2

実装によって異なります。私はJAVAにあまり詳しくありませんが、これらの操作はすべてトラバーサル操作であるようです（最も低い要素を取得し、最も高い要素を取得し、次に高くまたは次に低くなります）。

ツリーがAVLツリーのような自己平衡二分探索木として実装されている場合、または他の種類の平衡ツリー構造の場合、平均ケースと最悪ケースのO（log n）時間を調べます。各操作、およびO（1）の最良のケース。

于 2011-03-07T00:59:21.780 に答える