Tajuk artikel hendaklah: Apakah Kerumitan Masa Big-O Pelaksanaan Koleksi Java?
- Linda Hamiltonasal
- 2024-10-28 02:33:31772semak 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!
Artikel berkaitan
Lihat lagi- Berikut ialah beberapa pilihan tajuk, memfokuskan pada soalan teras dan penyelesaian \"dialog tanpa model\": Pilihan 1 (Terus & Ringkas): * Cara Membuka JFrames Secara Berurutan Tanpa Menggunakan Butang
- Bagaimanakah Pemalam Maven Shade Memperkemas Perlaksanaan Aplikasi dan Menyelesaikan Konflik Ketergantungan?
- Bagaimana Untuk Mencapai Ketidakbolehubahan Sebenar untuk Tatasusunan Primitif di Jawa?
- Bagaimana untuk Menyesuaikan Penampilan Teks dalam Java Menggunakan Fon, Saiz dan Warna Dipratentukan?
- Bagaimanakah Pemasa Boleh Digunakan untuk Mencipta Pergerakan Objek Tertunda Secara Rawak?