Tóm tắt Big-O cho Bộ sưu tập Java Triển khai khung?

Question

Tôi có thể dạy sớm "khóa học về sự cố Java". Mặc dù có thể giả định rằng các thành viên khán giả sẽ biết ký hiệu Big-O, có thể không an toàn để giả định rằng họ sẽ biết thứ tự của các hoạt động khác nhau trên các triển khai bộ sưu tập khác nhau là gì.

tôi có thể mất nhiều thời gian để tạo ra một ma trận tóm tắt bản thân mình, nhưng nếu nó đã ra khỏi đó trong phạm vi công cộng ở đâu đó, tôi chắc chắn muốn tái sử dụng nó (với tín dụng thích hợp, tất nhiên.)

Bất cứ ai cũng có bất kỳ con trỏ?

Answer 1

Trang web này khá tốt nhưng không cụ thể đối với Java: http://bigocheatsheet.com/

Answer 2

Javadocs từ Sun cho mỗi lớp thu sẽ thường cho bạn biết chính xác những gì bạn muốn. HashMap, ví dụ:

thực hiện này cung cấp liên tục thời gian hiệu suất cho các thao tác cơ bản (get và put), giả định các hàm băm phân tán các yếu tố đúng trong xô. Lặp lại các khung nhìn bộ sưu tập yêu cầu tỷ lệ thời gian với "dung lượng" của thể hiện HashMap (số lượng nhóm) cộng với kích thước của nó (số ánh xạ khóa-giá trị).

TreeMap:

thực hiện này cung cấp đảm bảo log (n) thời gian chi phí cho containsKey, có được, đặt và gỡ bỏ các hoạt động.

TreeSet:

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

(tôi nhấn mạnh)

Answer 3

Cuốn sách Java Generics and Collections có thông tin này (trang: 188, 211, 222, 240).

Danh sách triển khai:

     get add contains next remove(0) iterator.remove 
ArrayList    O(1) O(1) O(n)  O(1) O(n)  O(n) 
LinkedList   O(n) O(1) O(n)  O(1) O(1)  O(1) 
CopyOnWrite-ArrayList O(1) O(n) O(n)  O(1) O(n)  O(n) 

Set triển khai:

     add  contains next  notes 
HashSet    O(1)  O(1)  O(h/n) h is the table capacity 
LinkedHashSet   O(1)  O(1)  O(1) 
CopyOnWriteArraySet O(n)  O(n)  O(1) 
EnumSet    O(1)  O(1)  O(1) 
TreeSet    O(log n) O(log n) O(log n) 
ConcurrentSkipListSet O(log n) O(log n) O(1) 

Bản đồ triển khai:

     get  containsKey next  Notes 
HashMap    O(1)  O(1)  O(h/n) h is the table capacity 
LinkedHashMap   O(1)  O(1)  O(1) 
IdentityHashMap  O(1)  O(1)  O(h/n) h is the table capacity 
EnumMap    O(1)  O(1)  O(1) 
TreeMap    O(log n) O(log n) O(log n) 
ConcurrentHashMap  O(1)  O(1)  O(h/n) h is the table capacity 
ConcurrentSkipListMap O(log n) O(log n) O(1) 

triển khai Queue:

     offer peek poll  size 
PriorityQueue   O(log n) O(1) O(log n) O(1) 
ConcurrentLinkedQueue O(1)  O(1) O(1)  O(n) 
ArrayBlockingQueue O(1)  O(1) O(1)  O(1) 
LinkedBlockingQueue O(1)  O(1) O(1)  O(1) 
PriorityBlockingQueue O(log n) O(1) O(log n) O(1) 
DelayQueue   O(log n) O(1) O(log n) O(1) 
LinkedList   O(1)  O(1) O(1)  O(1) 
ArrayDeque   O(1)  O(1) O(1)  O(1) 
LinkedBlockingDeque O(1)  O(1) O(1)  O(1) 

Đáy của javadoc cho gói java.util chứa một số liên kết tốt:

• Collections Overview có một bảng tóm tắt tốt đẹp.
• Annotated Outline liệt kê tất cả các triển khai trên một trang.

Answer 4

Anh chàng ở trên đã so sánh cho HashMap/HashSet so với TreeMap/TreeSet.

tôi sẽ nói về ArrayList vs LinkedList:

ArrayList:

• O (1) get()
• khấu hao O (1) add()
• nếu bạn chèn hoặc xóa một phần tử trong giữa sử dụng ListIterator.add() hoặc Iterator.remove(), sẽ là O (n) để dịch chuyển tất cả các phần tử sau

LinkedList:

• O (n) get()
• O (1) add()
• nếu bạn chèn hoặc xóa một yếu tố ở giữa sử dụng ListIterator.add() hoặc Iterator.remove(), nó sẽ là O (1)