java - TreeSet 操作の複雑さ

Question

• java.util.TreeSetのhigher()の複雑さは?
• 昇順ですべての要素にアクセスする場合の (償却後の) 複雑さはどれくらいになるでしょうか?

説明では、「この実装は、基本的な操作 (追加、削除、および含む) の保証された log(n) 時間コストを提供します」とだけ述べています。

Answer 1

higher() も log(n) になると思います。より高い要素を見つけるには、higher() への入力を挿入する場所を見つけ、1 つ「上」に移動すると、log(n) 時間になります。

要素を繰り返し処理する場合、n 時間を見ています。contains を使用して購入する各要素にアクセスすると、n log(n) 時間になります。