java - Java における TreeSet メソッドの計算上の複雑さ

Question

Java の TreeSet メソッドの計算の複雑さは、AVLTree の計算の複雑さと同じですか?

具体的には、次のメソッドの計算量を知りたい: 1.add 2.remove 3.first 4.last 5. floor 6.higher

メソッドの説明に関する Java Doc: http://docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html

AVL ツリーの場合、すべて O(logn)? 上記の TreeSet メソッドの複雑さは何ですか?

Answer 1

単一の要素で動作する操作は、O(1) 比較または O(ln N) ノード検索時間である最初と最後を除いて、すべて O(ln n) 比較です。

comparison()、iterator()、clear()、first()、isEMpty()、size()、last()、pollFirst()、pollLast() は O(1)

add()、ceiling()、contains()、floor()、headSet()、higher()、lower()、remove()、subSet()、tailSet()はO(ln N)

clone()、equals()、hashCode()、toArray()、toString() は O(n)