Kompleksitas Operasi Koleksi

Dua koleksi bisa menyelesaikan pekerjaan yang sama dengan hasil identik, tetapi berbeda kecepatan saat data membesar. Perbedaan itu diukur dengan notasi Big-O: deskripsi bagaimana jumlah langkah bertambah ketika jumlah data n bertambah. Bab ini merangkum biaya operasi koleksi yang sudah kita pelajari, lalu menunjukkan perbedaannya pada satu operasi yang paling sering dipakai: pengecekan keanggotaan.

Tiga Taraf Big-O yang Sering Dijumpai #

• O(1) — konstan: jumlah langkah tetap berapa pun ukuran data. Contoh: akses indexer pada Dictionary.
• O(log n) — logaritmik: data bertambah dua kali lipat, langkah hanya bertambah sedikit. Contoh: pencarian pada SortedDictionary.
• O(n) — linier: jumlah langkah sebanding dengan jumlah data. Contoh: Contains pada List yang memindai dari depan.

Perbedaan pada Contains #

Contoh berikut memeriksa nama yang sama pada List dan HashSet. Hasilnya identik, tetapi jalannya berbeda: List membandingkan elemen satu per satu dari awal, sedangkan HashSet langsung menuju posisi yang dihitung dari hash nilai.

List<string> namaList = new List<string> { "Budi", "Siti", "Andi", "Rina" };
HashSet<string> namaSet = new HashSet<string> { "Budi", "Siti", "Andi", "Rina" };

Console.WriteLine($"List.Contains(\"Rina\"): {namaList.Contains("Rina")}");
Console.WriteLine($"HashSet.Contains(\"Rina\"): {namaSet.Contains("Rina")}");
Console.WriteLine($"List.Contains(\"Tono\"): {namaList.Contains("Tono")}");
Console.WriteLine($"HashSet.Contains(\"Tono\"): {namaSet.Contains("Tono")}");

Output yang Dihasilkan:

List.Contains("Rina"): True
HashSet.Contains("Rina"): True
List.Contains("Tono"): False
HashSet.Contains("Tono"): False

Mari kita telaah hasilnya:

1. Baris 1-2: Kedua koleksi berisi empat nama yang sama persis.
2. Baris 4-5: Pencarian "Rina" mengembalikan True pada keduanya; pada List, pencarian berhenti setelah empat perbandingan karena nama berada di posisi terakhir.
3. Baris 6-7: Pencarian "Tono" yang tidak ada memaksa List memeriksa seluruh empat elemen sebelum menyimpulkan False; HashSet tetap selesai dalam satu langkah penunjukan posisi.

Pada empat elemen, selisihnya tidak terasa. Pada empat puluh ribu elemen, selisihnya nyata: pencarian O(1) tetap stabil, sementara pencarian O(n) makin lama seiring data bertambah.

Tabel Kompleksitas Operasi Koleksi #