Kasus Terbaik, Terburuk, & Rata-rata
Tiga Cara Mengukur Algoritma
Biaya setiap algoritma bergantung pada masukan. Dua masukan dengan ukuran yang sama dapat menghasilkan waktu berjalan yang sangat berbeda. Analisis kompleksitas merumuskan tiga perspektif tentang variasi itu.
Kasus terbaik — Ω (Omega): masukan yang membuat algoritma selesai paling cepat. Untuk pencarian linier di atas daftar N item: Ω(1) — target menempati posisi pertama. Satu perbandingan, selesai.
Kasus terburuk — O (Big O): masukan yang membuat algoritma selesai paling lambat. Untuk pencarian linier: O(N) — target duduk di akhir daftar, atau tidak muncul sama sekali. Setiap elemen memerlukan inspeksi.
Kasus rata-rata — Θ (Theta): biaya yang diharapkan di atas semua kemungkinan masukan, dengan asumsi distribusi seragam. Untuk pencarian linier dengan target sama-sama mungkin menempati salah satu dari N posisi: Θ(N/2) = Θ(N). Konstanta 1/2 jatuh karena Theta mengekspresikan pertumbuhan asimptotik yang ketat, bukan koefisien yang tepat.
Mengapa Kasus Terburuk Mendominasi
Sistem harus menangani kasus terburuk. Kueri database yang rata-rata 10 milidetik tetapi kadang-kadang membutuhkan 60 detik menghasilkan kegagalan yang terlihat oleh pengguna. Insinyur merancang batas kasus terburuk sehingga kinerja tetap dapat diprediksi terlepas dari masukan. Analisis kasus rata-rata memiliki nilai dalam pengaturan probabilistik, tetapi analisis kasus terburuk memberikan jaminan.
Analisis Kasus Pencarian Biner
Pencarian biner hanya bekerja pada larik yang diurutkan. Pada setiap langkah: bandingkan target dengan elemen di titik tengah. Jika target sama dengan titik tengah, kembalikan. Jika target lebih kecil, rekursi pada setengah kiri. Jika lebih besar, rekursi pada setengah kanan.
Setiap perbandingan menghilangkan setengah dari kandidat yang tersisa.
Pertumbuhan Memori & Pertukaran Waktu-Ruang
Menghitung Memori, Bukan Operasi
Kompleksitas waktu mengukur jumlah operasi yang dijalankan algoritma. Kompleksitas ruang mengukur memori ekstra yang dialokasikan di luar masukan. Keduanya penting dalam sistem produksi: algoritma cepat yang mengalokasikan memori O(N²) akan menghabiskan server.
Ruang O(1): memori ekstra konstan terlepas dari N. Pengurutan di tempat (misalnya pengurutan penyisipan) menukar elemen di dalam larik asli. Ini menggunakan segenggam variabel sementara — O(1) tidak peduli seberapa besar lariknya.
Ruang O(N): memori proporsional dengan ukuran masukan. Membuat salinan larik elemen N memerlukan slot N. Membangun set hash dari daftar string N menyimpan hingga entri N.
Ruang O(N²): memori proporsional dengan N². Membangun matriks ketetanggaan N×N untuk grafik dengan N simpul memerlukan sel N². Pada N = 10.000 simpul, itu adalah 10^8 entri — ratusan megabita untuk grid boolean sederhana.
Pertukaran Waktu-Ruang
Salah satu gerakan fundamental dalam desain algoritma: menukar ruang untuk waktu, atau waktu untuk ruang.
Tabel hash menggunakan ruang ekstra O(N) untuk mencapai pencarian O(1). Tanpa tabel hash, pemindaian di atas daftar mencapai pencarian O(N) dengan ruang ekstra O(1). Tabel hash membayar memori untuk membeli kecepatan.
Memoisasi menyimpan hasil yang telah dihitung sebelumnya (ruang O(N) atau lebih) untuk menghindari perhitungan ulang. Fibonacci rekursif tanpa memoisasi berjalan dalam waktu O(2^N). Dengan memoisasi: waktu O(N) dan ruang O(N). Investasi ruang menyusutkan waktu secara eksponensial.
Kamus Hash vs Daftar Terurut
Bandingkan dua strategi untuk menghitung kemunculan kata dalam dokumen N kata:
Strategi A: kamus (peta hash). Masukkan setiap kata; naikkan perhitungannya.
Strategi B: pertahankan daftar terurut kata-kata yang terlihat; gunakan pencarian biner untuk memeriksa keanggotaan sebelum menyisipkan.
Analisis Diamortisasi: Menyebarkan Biaya
Ketika Pengeluaran Sesekali Tidak Merusak Kinerja Rata-rata
Beberapa operasi kadang-kadang mahal tetapi murah pada rata-rata di seluruh urutan. Analisis diamortisasi menghitung biaya rata-rata per operasi di seluruh urutan — bukan biaya kasus terburuk dari satu operasi.
Larik dinamis (daftar Python, ArrayList Java): dimulai dengan kapasitas 1. Ketika penuh, menggandakan kapasitas. Penggandaan menyalin semua elemen yang ada: pekerjaan O(N) untuk satu penambahan. Tetapi penggandaan jarang. Setelah N total penambahan, berapa total operasi penyalinan yang terjadi?
Penggandaan terjadi pada ukuran 1, 2, 4, 8, ..., N/2. Jumlah penyalinan: 1 + 2 + 4 + ... + N/2. Ini adalah deret geometri yang menjumlahkan N − 1 total penyalinan di seluruh N penambahan. Penyalinan rata-rata per penambahan: (N − 1) / N < 1, jadi O(1) diamortisasi per penambahan terlepas dari biaya kasus terburuk O(N) per penggandaan.
Mengapa Analisis Diamortisasi Penting
Sistem yang kadang-kadang berhenti untuk mengubah ukuran, menyeimbangkan kembali, atau memadatkan struktur mungkin tampak memiliki operasi individu kasus terburuk yang menakutkan. Analisis diamortisasi mengungkapkan bahwa alarm adalah salah: peristiwa mahal yang jarang dibayar oleh banyak peristiwa murah. Memahami biaya diamortisasi mencegah rekayasa berlebihan: menambahkan kompleksitas untuk menghindari operasi O(N) yang jarang yang menyumbang hanya O(1) diamortisasi adalah pekerjaan yang terbuang sia-sia.
Lebih Dalam: Kursus unhamming menerapkan analisis kompleksitas pada cacat dunia nyata dalam perangkat lunak produksi. Lihat Bab yang Hilang: Kompleksitas Algoritma & MOAD-0001: Cacat Sedimen.
Penyisipan Diamortisasi Tabel Hash
Tabel hash dimulai kosong dan menggandakan kapasitas setiap kali faktor beban melebihi 0,75. Menyisipkan 1.000 elemen memicu tepat 10 penggandaan pada kapasitas 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.