Tajuk artikel hendaklah: Apakah Kerumitan Masa Big-O Pelaksanaan Koleksi Java?

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!