Best, Worst, & Average Case
Tiga Cara Untuk Mengukur Algoritma
Biaya setiap algoritma tergantung pada inputnya. Dua input yang sama ukurannya dapat menghasilkan waktu eksekusi yang sangat berbeda. Analisis kompleksitas mem formalisasikan tiga perspektif pada variasi tersebut.
Best case — Ω (Omega): input yang membuat algoritma selesai paling cepat. Untuk pencarian linear di atas daftar N item: Ω(1) — target mengisi posisi pertama. Satu perbandingan, selesai.
Worst case — O (Big O): input yang membuat algoritma selesai paling lambat. Untuk pencarian linear: O(N) — target berada di posisi terakhir dalam daftar, atau tidak muncul sama sekali. Setiap elemen memerlukan pemeriksaan.
Average case — Θ (Theta): biaya rata-rata di atas semua input mungkin, dengan asumsi distribusi seragam. Untuk pencarian linear dengan target secara bersamaan mungkin mengisi salah satu dari N posisi: Θ(N/2) = Θ(N). Konstanta 1/2 jatuh karena Theta menggambarkan pertumbuhan asimetris, bukan koefisien yang tepat.
Mengapa Worst Case Dominan
Sistem harus mengatasi kasus terburuk. Pertanyaan basis data yang rata-rata 10 ms tetapi kadang-kadang memakan 60 detik menghasilkan kegagalan yang terlihat oleh pengguna. Insinyur merancang untuk batas terburuk agar kinerja tetap prediktif meskipun input. Analisis kasus rata-rata memiliki nilai dalam pengaturan probabilistik, tetapi analisis kasus terburuk memberikan jaminan.
Analisis Kasus Binary Search
Pencarian biner hanya berfungsi pada array terurut. Di setiap langkah: bandingkan target dengan elemen di titik tengah. Jika target sama dengan titik tengah, kembalikan. Jika target lebih kecil, rekursif pada setengah kiri. Jika lebih besar, rekursif pada setengah kanan.
Setiap perbandingan menghilangkan setengah calon yang tersisa.
Pertumbuhan Memori & Trandaoff Waktu-Ruang
Hitung Memori, Bukan Operasi
Kompleksitas waktu mengukur jumlah operasi yang dieksekusi oleh sebuah algoritma. Kompleksitas ruang mengukur alokasi memori tambahan di luar inputnya. Keduanya penting dalam sistem produksi: sebuah algoritma cepat yang mengalokasikan O(N²) memori akan habis sumber servernya.
O(1) ruang: konstan alokasi memori meskipun N. Mengurutkan secara in-place (misalnya, pengurutan pengisian) menukar elemen di array asli. Menggunakan beberapa variabel sementara - O(1) tanpa tergantung besar arraynya.
O(N) ruang: memori proporsional dengan ukuran input. Membuat salinan N-element dari array membutuhkan N slot. Membangun set hash dari daftar N string menyimpan hingga N entri.
O(N²) ruang: memori proporsional dengan N². Membangun sebuah matrix sejarah dekat N×N untuk grafik dengan N vertex membutuhkan N² sel. Pada N = 10.000 vertex, itu adalah 10^8 entri - ratusan megabyte untuk sebuah grid boolean sederhana.
Trandaoff Waktu-Ruang
Salah satu gerakan fundamental dalam desain algoritma: tukar ruang untuk waktu, atau waktu untuk ruang.
Hash tables menggunakan O(N) ruang tambahan untuk mencapai O(1) pencarian. Tanpa tabel hash, skanner atas daftar mencapai O(N) pencarian dengan O(1) ruang tambahan. Tabel hash membayar memori untuk membeli kecepatan.
Memoization menyimpan hasil yang pernah dihitung sebelumnya (O(N) atau lebih ruang) untuk menghindari menghitungnya lagi. Fibonacci rekursif tanpa memoization berjalan dalam O(2^N) waktu. Dengan memoization: O(N) waktu dan O(N) ruang. Investasi ruang mengurangi waktu secara eksponensial.
Kamus Hash vs Daftar Terurut
Bandingkan dua strategi untuk menghitung kejadian kata dalam dokumen yang memiliki N kata:
Strategi A: sebuah kamus (hash map). Masukkan setiap kata; tambahkan hitungannya.
Strategi B: pertahankan daftar yang terurut dari kata-kata yang dilihat; gunakan pencarian biner untuk mengecek keanggotaan sebelum memasukkan.
Analisis Amortisasi: Menyebar Biaya
Ketika Biaya Sesekali Tidak Menghancurkan Performa Rata-rata
Beberapa operasi kadang-kadang mahal tetapi murah rata-rata di seluruh urutan melalui analisis amortisasi. Analisis amortisasi menghitung biaya rata-rata per operasi di seluruh urutan - bukan biaya terburuk dari operasi tunggal.
Array Dinamis (daftar Python, ArrayList Java): dimulai dengan kapasitas 1. Ketika penuh, menggandakan kapasitas. Menggandakan menyalin semua elemen yang ada: O(N) kerja untuk satu tambahan. Tetapi penggandian jarang terjadi. Setelah N tambahan total, berapa banyak operasi salinan total yang terjadi?
Penggandian terjadi pada ukuran 1, 2, 4, 8, ..., N/2. Hitungan salinan: 1 + 2 + 4 + ... + N/2. Ini adalah serangkaian geometris yang jumlahnya N − 1 salinan total di seluruh N tambahan. Rata-rata salinan per tambahan: (N − 1) / N < 1, jadi O(1) amortized per tambahan meskipun biaya terburuk per penggandian O(N)
Mengapa Analisis Amortisasi Penting
Sistem yang kadang-kadang berhenti untuk menggandakan, menyeimbangkan, atau mempadatkan struktur mungkin tampak memiliki operasi individu yang mengkhawatirkan O(N). Analisis amortisasi menunjukkan bahwa kekhawatiran itu salah: yang mahal jarang terjadi dibayar oleh banyak yang murah. Memahami biaya amortisasi mencegah over-engineering: menambahkan kompleksitas untuk menghindari operasi O(N) yang jarang terjadi yang hanya menambah biaya amortisasi O(1) adalah pekerjaan yang sia-sia.
Mendalam: Kursus unhamming menerapkan analisis kompleksitas pada kecacatan nyata di perangkat lunak produksi. Lihat [Bab yang Hilang: Kompleksitas Algoritma](/en/un/unhamming_algorithmic_complexity) & [MOAD-0001: Kecacatan Sedimen](/en/un/unhamming_moad_sedimentary).
Amortized Insert Hash Table
Hash table dimulai dari kosong dan menggandakan kapasitasnya saat faktor muatan melebihi 0,75. Menginsert 1.000 elemen menimbulkan tepat 10 kali pembesaran pada kapasitas 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.