Tính toán phức tạp của các hoạt động TreeSet trong Java?

Question

Tôi đang cố gắng làm sáng tỏ một số điều liên quan đến sự phức tạp trong một số hoạt động của TreeSet. Trên javadoc nó nói:

"thực hiện này cung cấp đảm bảo log (n) Chi phí thời gian cho các thao tác cơ bản (thêm, xóa và chứa)."

Cho đến nay rất tốt. Câu hỏi của tôi là những gì xảy ra trên addAll(), RemoveAll() vv Ở đây javadoc cho Set nói:

"Nếu bộ sưu tập theo quy định cũng là một tập hợp , hoạt động có hiệu quả addAll đổi thiết lập này để nó giá trị là công đoàn của hai bộ. "

Nó chỉ giải thích kết quả hợp lý của hoạt động hay là nó đưa ra một gợi ý về sự phức tạp? Ý tôi là, nếu hai bộ được biểu diễn bằng ví dụ: cây đỏ-đen sẽ tốt hơn nếu bằng cách nào đó tham gia vào cây hơn là "thêm" từng phần tử của cái này sang phần khác.

Trong mọi trường hợp, có cách nào kết hợp hai TreeSets thành một với độ phức tạp O (logn) không?

Cảm ơn bạn trước. :-)

Answer 1

Bạn có thể hình dung cách tối ưu hóa các trường hợp đặc biệt thành O(log n), nhưng trường hợp xấu nhất phải là trong đó m và n là số phần tử trong mỗi cây.

Edit:

http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm

Mô tả một thuật toán trường hợp đặc biệt có thể tham gia cây trong O(log(m + n)) nhưng lưu ý những hạn chế: tất cả các thành viên của S1 phải nhỏ hơn tất cả các thành viên của S2. Đây là những gì tôi có nghĩa là có tối ưu hóa đặc biệt cho các trường hợp đặc biệt.

Answer 2

Theo bài viết trên blog này:
http://rgrig.blogspot.com/2008/06/java-api-complexity-guarantees.html
đó là O (n log n). Bởi vì tài liệu hướng dẫn không đưa ra gợi ý về độ phức tạp, bạn có thể muốn viết thuật toán của riêng mình nếu hiệu suất là quan trọng đối với bạn.

Answer 3

Nhìn vào nguồn java cho TreeSet, có vẻ như nó nếu bộ sưu tập được truyền vào là một SortedSet thì nó sử dụng thuật toán thời gian O (n). Nếu không, nó gọi super.addAll, mà tôi đoán sẽ dẫn đến O (n logn).

EDIT - đoán tôi đọc mã quá nhanh, TreeSet chỉ có thể sử dụng O (n) thuật toán nếu nó sao lưu bản đồ trống

Answer 4

Nó không phải là có thể thực hiện việc sáp nhập của cây hoặc tham gia bộ như trong Disjoint- thiết lập cấu trúc dữ liệu vì bạn không biết liệu các phần tử trong 2 cây có bị phân tách hay không. Vì cấu trúc dữ liệu có kiến ​​thức về nội dung trong các cây khác, cần phải kiểm tra xem một phần tử có tồn tại trong cây khác trước khi thêm vào hay ít nhất là cố thêm nó vào cây khác và hủy thêm nó nếu bạn tìm thấy nó cách. Vì vậy, nó phải là O (MlogN)