Tajuk artikel hendaklah: Apakah Kerumitan Masa Big-O Pelaksanaan Koleksi Java?
- Linda Hamiltonasal
- 2024-10-28 02:33:31839semak imbas
Pelaksanaan Rangka Kerja Java Collections: Ringkasan Big-O
Apabila mengajar "Java crash-course," adalah penting untuk mengetahui kerumitan masa Big-O yang dikaitkan dengan pelbagai pelaksanaan koleksi. Walaupun ahli penonton mungkin biasa dengan notasi Big-O, tidak mungkin mereka akan mengetahui kerumitan khusus untuk operasi yang berbeza pada koleksi tertentu.
Nasib baik, buku "Java Generics and Collections" memberikan cerapan berharga tentang kerumitan ini . Artikel ini meringkaskan maklumat daripada buku, menyediakan jadual terperinci untuk setiap jenis koleksi: senarai, set, peta dan baris gilir.
Senarai Pelaksanaan:
| Operation | ArrayList | LinkedList | CopyOnWriteArrayList |
|---|---|---|---|
| get | O(1) | O(n) | O(1) |
| add | O(1) | O(1) | O(n) |
| contains | O(n) | O(n) | O(n) |
| next | O(1) | O(1) | O(1) |
| remove(0) | O(n) | O(1) | O(n) |
| iterator.remove | O(n) | O(1) | O(n) |
Tetapkan Pelaksanaan:
| Operation | HashSet | LinkedHashSet | CopyOnWriteArraySet | EnumSet | TreeSet | ConcurrentSkipListSet |
|---|---|---|---|---|---|---|
| add | O(1) | O(1) | O(n) | O(1) | O(log n) | O(log n) |
| contains | O(1) | O(1) | O(n) | O(1) | O(log n) | O(log n) |
| next | O(h/n) | O(1) | O(1) | O(1) | O(log n) | O(1) |
| Notes | h is the table capacity |
Pelaksanaan Peta:
| Operation | HashMap | LinkedHashMap | IdentityHashMap | EnumMap | TreeMap | ConcurrentHashMap | ConcurrentSkipListMap |
|---|---|---|---|---|---|---|---|
| get | O(1) | O(1) | O(1) | O(1) | O(log n) | O(1) | O(log n) |
| containsKey | O(1) | O(1) | O(1) | O(1) | O(log n) | O(1) | O(log n) |
| next | O(h/n) | O(1) | O(h/n) | O(1) | O(log n) | O(h/n) | O(1) |
| Notes | h is the table capacity |
Pelaksanaan Beratur:
| Operation | PriorityQueue | ConcurrentLinkedQueue | ArrayBlockingQueue | LinkedBlockingQueue | PriorityBlockingQueue | DelayQueue | LinkedList | ArrayDeque | LinkedBlockingDeque |
|---|---|---|---|---|---|---|---|---|---|
| offer | O(log n) | O(1) | O(1) | O(1) | O(log n) | O(log n) | O(1) | O(1) | O(1) |
| peek | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) |
| poll | O(log n) | O(1) | O(1) | O(1) | O(log n) | O(log n) | O(1) | O(1) | O(1) |
| size | O(1) | O(n) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) |
Atas ialah kandungan terperinci Tajuk artikel hendaklah: Apakah Kerumitan Masa Big-O Pelaksanaan Koleksi Java?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!