Setiap Kelas Kompleksitas Menggambar Kurva
Gambar Biaya Terhadap Ukuran Input
Tempatkan ukuran input N pada sumbu x. Tempatkan biaya (operasi, waktu) pada sumbu y. Setiap kelas kompleksitas menghasilkan kurva yang unik. Anda dapat mengenali tingkat pertumbuhan algoritma dari bentuk kurva performanya.
O(1) — garis horizontal datar. Fungsi f(N) = 1. Tanpa kemiringan. Biaya tidak pernah berubah terlepas dari N. Pencarian hash: entah tabelnya memiliki 10 atau 10.000.000 elemen, satu komputasi hash melompat ke bucket yang benar.
O(log N) — kurva naik perlahan, kemiringan menurun. Pada N = 1.000.000: biaya ≈ 20 operasi. Kurva naik dengan tajam pada N kecil, lalu rata. Setiap penggandaan N menambah biaya satu unit.
O(N) — garis diagonal lurus. Kemiringan = 1 (dalam arti asimptotik). Biaya tumbuh dengan laju yang sama dengan N. Jika N tiga kali lipat, biaya juga tiga kali lipat.
O(N log N) — diagonal yang lebih miring dengan sedikit keruncingan ke atas. Berada di atas O(N) tetapi di bawah O(N²). Faktor log menambahkan multiplier yang tumbuh perlahan pada kemiringan linear.
O(N²) — parabola yang membuka ke atas. Kemiringan bertambah seiring pertumbuhan N. Pada N = 10: biaya = 100. Pada N = 100: biaya = 10.000. Pada N = 1.000: biaya = 1.000.000.
Jarak Meningkat
Perbandingan O(N²) / O(N) = N. Jarak antara parabola dan diagonal semakin lebar seiring pertumbuhan N. Pada N = 10: 10× jarak. Pada N = 100: 100× jarak. Pada N = 1.000: 1.000× jarak. Pada N = 50.000: 50.000× jarak. Jarak tersebut sama dengan N — selalu.
Menghitung Jarak Skala
Sebuah grafik dependensi besar memiliki 50.000 paket (N = 50.000). Satu algoritma berjalan dalam waktu O(N). Yang kedua berjalan dalam O(N²). Pada N ini, perbandingan O(N²)/O(N) = N = 50.000.
Membagi Segmen Garis
Pencarian Biner sebagai Pembagian Berulang
Sebuah array terurut dengan N elemen membentuk segmen garis panjang N. Pencarian biner secara berkali-kali membagi segmen ini:
1. Menunjuk ke titik tengah dari segmen yang tersisa.
2. Jika target < tengah: setengah kanan hilang. Rekursif pada setengah kiri.
3. Jika target > tengah: setengah kiri hilang. Rekursif pada setengah kanan.
4. Jika target = tengah: selesai.
Setelah k pembagian, segmen yang tersisa memiliki panjang N / 2^k. Pencarian berakhir ketika panjang itu sama dengan 1:
N / 2^k = 1 → 2^k = N → k = log₂N
Jadi, pencarian biner pada N elemen membutuhkan maksimum log₂N perbandingan.
Pembagian & Penggandaan: Dua Sisi dari Kurva yang Sama
Pembagian dan penggandaan adalah invers geometris. Kurva eksponensial 2^k dan kurva logaritma log₂N adalah refleksi satu sama lain di atas garis y = x.
Pertimbangkan lipat kertas: lembaran mulai dari 0,1 mm tebal. Setiap lipatan menggandakan ketebalan. Setelah 42 lipatan: 0,1 mm × 2^42 ≈ 439.980 km — melebihi bulan (384.400 km). Pencarian biner menjalankan invers: mulai dari N elemen, setiap langkah mengurangi jumlah setengah, mencapai 1 elemen dalam log₂N langkah.
Geometri: pembagian adalah operasi yang mirip diri sendiri. Setiap pembagian menghasilkan dua setengah yang terlihat identik dalam struktur dengan keseluruhan. Rekursif dan logaritma membagi sifat ini yang mirip diri sendiri.
Perbandingan & Penggandaan
Sebuah array terurut mengandung 1.048.576 elemen. Catatan: 1.048.576 = 2^20.
Fungsi Hash sebagai Peta Geometri
Fungsi Hash sebagai Fungsi
Tabel hash menerjemahkan kunci ke bucket menggunakan fungsi hash:
bucket = hash(key) mod table_size
Ini adalah fungsi dalam arti matematis ketat: itu menerjemahkan domain (semua kunci yang mungkin) ke range (indeks bucket 0 hingga table_size - 1). Gambar geometris: kunci mengisi satu ruang; bucket mengisi yang lain. Fungsi hash memroyek kunci ke indeks bucket.
O(1) pencarian — lompat langsung, tidak ada pencarian. Fungsi hash menghitung indeks bucket dalam waktu konstan. Lompat langsung ke bucket tersebut. Tidak ada perambahan, tidak ada loop perbandingan.
Faktor muat. Pada faktor muat 0,75, 75% bucket berisi setidaknya satu elemen. Di atas ~0,9, kolisi meningkat: dua kunci hash ke bucket yang sama, membentuk rantai elemen di dalam bucket tersebut. Pencarian di rantai panjang mengurangi O(N) pada kasus terburuk.
Kualitas Distribusi sebagai Geometri
Fungsi hash yang baik menyebar kunci secara merata di semua bucket. Geometris: fungsi range menutupi domainnya merata. Setiap bucket menerima sekitar N / table_size kunci.
Fungsi hash yang buruk mengumpulkan kunci ke beberapa bucket. Geometris: range fungsi mengalami kolaps ke subset domainnya — kebanyakan kunci map ke beberapa titik yang sama. Bucket yang tersisa tetap kosong.
Koneksi ke MOAD-0001
Menggantikan daftar dengan set memperbaiki MOAD-0001 karena set menggunakan tabel hash secara internal. Skanning daftar O(N) → pencarian tabel hash O(1). Geometris: perambahan linear di sepanjang urutan berubah menjadi proyeksi langsung melalui fungsi. Urutan hilang; fungsi menggantikannya.
Menganalisis Fungsi Hash yang Tidak Baik
Sebuah tabel hash memiliki 1.000 buah wadah dan 900 elemen (faktor muat 0,9). Fungsi hash yang buruk mengirimkan 500 dari elemen tersebut ke wadah yang sama.