Persyaratan: Anda perlu menentukan jenis koleksi baca-saja, yang tidak akan menambahkan, menghapus, atau memodifikasi koleksi, tetapi hanya akan mengkueri koleksi. Kami berharapSemakin cepat kueri, semakin baik。
Perbandingan kumpulan umum
Saat menggambarkan kompleksitas algoritma, o(1), o(n), o(logn), o(logn), o(nlogn) biasanya digunakan untuk mengekspresikan kompleksitas waktu dari algoritma yang sesuai, yang merupakan ekspresi kompleksitas spatiotemporal algoritma. Ini digunakan tidak hanya untuk mewakili kompleksitas temporal, tetapi juga untuk mewakili kompleksitas spasial.
O diikuti oleh fungsi dalam tanda kurung yang menunjukkan hubungan antara waktu/ruang yang dikonsumsi oleh algoritme dan jumlah data yang dikembangkan. di mana n mewakili jumlah data input.
Misalnya, jika kompleksitas waktu adalah O(n), itu berarti jumlah data meningkat beberapa kali, dan konsumsi waktu juga meningkat beberapa kali lipat. Misalnya, algoritma traversal umum. Contoh lain adalah kompleksitas waktu O(n^2), yang berarti bahwa ketika volume data meningkat n kali, dibutuhkan waktu untuk meningkatkan n kali kuadrat, yang merupakan kompleksitas waktu yang lebih tinggi daripada linier. Misalnya, penyortiran gelembung adalah algoritma O(n^2) yang khas, yang perlu dipindai n × n kali untuk mengurutkan n angka.
Contoh lain adalah O(logn), ketika data meningkat n kali, dibutuhkan waktu untuk meningkatkan waktu logn (log di sini didasarkan pada 2, misalnya, ketika data ditingkatkan 256 kali, waktu yang dibutuhkan hanya meningkat 8 kali lipat, yang lebih rendah dari linier. Pencarian biner adalah algoritma O (logn), yang menghilangkan setengah dari kemungkinan setiap kali ditemukan, dan pencarian dalam 256 data hanya perlu ditemukan 8 kali untuk menemukan target.
O(nlogn) sama, yaitu n dikalikan logn, ketika data ditingkatkan 256 kali, konsumsi waktu meningkat 256 * 8 = 2048 kali. Kompleksitas ini lebih tinggi daripada linearitas di bawah kuadrat. Gabungkan dan urutkan adalah kompleksitas waktu O(nlogn).
O(1) adalah kompleksitas spatiotemporal terendah, yaitu waktu/ruang yang dikonsumsi tidak bergantung pada ukuran data input, tidak peduli berapa kali data input ditingkatkan, waktu/ruang yang dikonsumsi tetap tidak berubah. Algoritma hashing adalah kompleksitas waktu O(1) yang khas, yang dapat menemukan target setelah satu perhitungan (terlepas dari konflik), tidak peduli seberapa besar datanya.
Artikel ini menggunakan pasangan BenchmarkDotNetDaftar、HashSet、SortedSet、KamusKueri untuk pembandingan, lihat yang berikut ini:
Kodenya adalah sebagai berikut:
Hasil pengujian: Menemukan Kunci pada Kamus atau HashSet jauh lebih cepat daripada mencari di List dan SortedSet. Kompleksitas waktu algoritma Kamus dan HashSet adalah O(1), dan untuk menghemat memori, Nilai Kamus tidak berguna bagi kami, jadi saya masih memilih penyimpanan HashSet.
|
Diposting pada 07/03/2022 16.47.50
|
|
|
|
Diposting pada 07/03/2022 23.09.48
|
Tuan tanah|
Diposting pada 09/03/2022 09.55.12
|
