Setiap Kelas Kompleksitas Menggambar Kurva
Gambarkan Biaya Terhadap Ukuran Input
Letakkan ukuran input N pada sumbu x. Letakkan biaya (operasi, waktu) pada sumbu y. Setiap kelas kompleksitas menghasilkan kurva yang berbeda. Anda dapat mengenali laju pertumbuhan algoritma dari bentuk kurva kinerjanya.
O(1) — garis horizontal datar. Fungsi f(N) = 1. Tidak ada kemiringan. Biaya tidak pernah berubah terlepas dari N. Pencarian tabel hash: apakah tabel berisi 10 atau 10.000.000 elemen, satu komputasi hash melompat ke bucket yang benar.
O(log N) — kurva meningkat lembut, kemiringan menurun. Pada N = 1.000.000: biaya ≈ 20 operasi. Kurva naik curam pada N kecil, kemudian mendatar. Setiap penggandaan N menambah tepat satu unit biaya.
O(N) — garis lurus diagonal. Kemiringan = 1 (dalam arti asimtotik). Biaya tumbuh dengan laju yang sama dengan N. Jika N berlipat tiga, biaya juga berlipat tiga.
O(N log N) — diagonal yang lebih curam dengan kurva naik yang sedikit. Terletak di atas O(N) tetapi di bawah O(N²). Faktor log menambahkan pengganda yang tumbuh perlahan ke kemiringan linier.
O(N²) — parabola membuka ke atas. Kemiringan meningkat seiring pertumbuhan N. Pada N = 10: biaya = 100. Pada N = 100: biaya = 10.000. Pada N = 1.000: biaya = 1.000.000.
Kesenjangan yang Berkembang
Rasio O(N²) / O(N) = N. Kesenjangan antara parabola dan diagonal melebar seiring pertumbuhan N. Pada N = 10: kesenjangan 10×. Pada N = 100: kesenjangan 100×. Pada N = 1.000: kesenjangan 1.000×. Pada N = 50.000: kesenjangan 50.000×. Kesenjangan sama dengan N — selalu.
Menghitung Kesenjangan Skala
Grafik ketergantungan besar berisi 50.000 paket (N = 50.000). Satu algoritma berjalan dalam waktu O(N). Yang kedua berjalan dalam O(N²). Pada N ini, rasio O(N²)/O(N) = N = 50.000.
Membagi Dua Segmen Garis
Pencarian Biner sebagai Pembagian Berulang
Array yang diurutkan dari N elemen membentuk segmen garis dengan panjang N. Pencarian biner secara berulang membagi dua segmen ini:
1. Tunjuk ke titik tengah segmen yang tersisa.
2. Jika target < titik tengah: separuh kanan hilang. Rekursi pada separuh kiri.
3. Jika target > titik tengah: separuh kiri hilang. Rekursi pada separuh kanan.
4. Jika target = titik 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 memerlukan paling banyak perbandingan log₂N.
Pembagian & Penggandaan: Dua Sisi dari Kurva yang Sama
Pembagian dan penggandaan adalah kebalikan geometris. Kurva eksponensial 2^k dan kurva logaritmik log₂N adalah refleksi satu sama lain di seluruh garis y = x.
Pertimbangkan lipatan kertas: lembaran dimulai dengan ketebalan 0,1 mm. Setiap lipatan menggandakan ketebalan. Setelah 42 lipatan: 0,1 mm × 2^42 ≈ 439.804 km — melampaui bulan (384.400 km). Pencarian biner berjalan sebaliknya: mulai dengan N elemen, setiap langkah membagi dua jumlahnya, mencapai 1 elemen dalam langkah log₂N.
Geometrinya: pembagian dua adalah operasi yang mirip dengan diri sendiri. Setiap pembagian menghasilkan dua bagian yang terlihat identik dalam struktur dengan keseluruhannya. Rekursi dan logaritma berbagi kesamaan diri ini.
Perbandingan & Penggandaan
Array yang diurutkan berisi 1.048.576 elemen. Catatan: 1.048.576 = 2^20.
Fungsi Hash sebagai Peta Geometris
Fungsi Hash sebagai Fungsi
Tabel hash memetakan kunci ke bucket menggunakan fungsi hash:
bucket = hash(key) mod table_size
Ini adalah fungsi dalam arti matematis yang ketat: ia memetakan domain (semua kunci yang mungkin) ke jangkauan (indeks bucket 0 hingga table_size − 1). Gambar geometris: kunci menempati satu ruang; bucket menempati ruang lain. Fungsi hash memproyeksikan kunci ke indeks bucket.
Pencarian O(1) — lompatan langsung, tidak ada pencarian. Fungsi hash menghitung indeks bucket dalam waktu konstan. Lompat langsung ke bucket itu. Tidak ada traversal, tidak ada loop perbandingan.
Faktor beban. Pada faktor beban 0,75, 75% bucket berisi setidaknya satu elemen. Di atas ~0,9, tabrakan meningkat: dua kunci di-hash ke bucket yang sama, membentuk rantai elemen di dalam bucket itu. Pencarian dalam rantai panjang merosot menjadi O(N) dalam kasus terburuk.
Kualitas Distribusi sebagai Geometri
Fungsi hash yang terdistribusi dengan baik menyebarkan kunci secara merata di semua bucket. Secara geometris: jangkauan fungsi mencakup kodomain-nya secara merata. Setiap bucket menerima sekitar N / table_size kunci.
Fungsi hash yang buruk mengelompokkan kunci ke dalam beberapa bucket. Secara geometris: jangkauan fungsi runtuh ke subset kodomain — sebagian besar kunci memetakan ke beberapa titik yang sama. Bucket yang tersisa kosong.
Koneksi ke MOAD-0001
Mengganti daftar dengan set memperbaiki MOAD-0001 karena set menggunakan tabel hash secara internal. Pemindaian daftar O(N) → pencarian tabel hash O(1). Secara geometris: traversal linier sepanjang urutan mengubah menjadi proyeksi langsung melalui fungsi. Urutan hilang; fungsi menggantinya.
Menganalisis Hash yang Terdistribusi Dengan Buruk
Tabel hash memiliki 1.000 bucket dan 900 elemen (faktor beban 0,9). Fungsi hash yang buruk mengirim 500 elemen tersebut ke bucket yang sama.