Ini materi penutup kategori Algoritma. Isinya soal memilih: tiap cara punya harga, biasanya waktu (berapa lama jalannya) atau memori (berapa banyak yang harus disimpan). Trade-off artinya menukar satu dengan yang lain, misalnya memakai memori lebih banyak supaya kodenya jauh lebih cepat.
🧪 Tebakan cepat: datamu cuma 50 angka, dan kodenya jalan sekali sehari. Perlu mengganti dua loop bersarang dengan cara yang lebih canggih? Tebak dulu, jawabannya ada di bagian "Kapan yang lambat justru tepat".
Seberapa besar n kamu?
Big-O menggambarkan bagaimana kerja sebuah cara tumbuh waktu datanya (n) membesar. O(n): datanya dua kali lipat, waktunya kira-kira dua kali lipat. O(n²), misalnya dua loop bersarang: datanya dua kali lipat, waktunya kira-kira empat kali lipat. Patokan kasarnya, komputer bisa menjalankan sekitar 100 juta operasi sederhana per detik.
const n = 5000;
const perSecond = 100000000; // patokan kasar: operasi sederhana per detik
console.log(n * n); // 25000000 operasi untuk O(n²)
console.log((n * n) / perSecond); // 0.25 detik
console.log((n * Math.log2(n)) / perSecond); // sekitar 0.0006 detik untuk O(n log n)
n * nadalah banyaknya operasi O(n²) untuk 5.000 data: 25 juta.- Dibagi
perSecond, hasilnya perkiraan waktu: seperempat detik. Masih aman. Math.log2(n)adalah log n: berapa kalinbisa dibagi dua sampai tinggal 1. Untuk 5.000 cuma sekitar 12, jadi O(n log n) jauh lebih ringan.
Dari hitungan itu keluar patokan berikut, untuk kira-kira 1 detik:
n sekitar |
Yang masih muat | Contoh |
|---|---|---|
| 10 | O(n!) | mencoba semua urutan (backtracking) |
| 5.000 | O(n²) | dua loop bersarang |
| 100.000 | O(n log n) | sort dulu, lalu binary search atau two pointer |
| 1.000.000 | O(n) atau O(n log n) | sekali lewat, misalnya hash map atau sliding window |
| 1.000.000.000 | O(log n) | binary search, atau rumus |
Tukar memori dengan waktu
Cari tahu apakah sebuah array punya angka kembar (duplikat):
function adaDuplikatLambat(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) return true;
}
}
return false;
}
function adaDuplikatCepat(arr) {
const sudahDilihat = new Set();
for (const x of arr) {
if (sudahDilihat.has(x)) return true;
sudahDilihat.add(x);
}
return false;
}
console.log(adaDuplikatLambat([3, 1, 4, 1])); // true
console.log(adaDuplikatCepat([3, 1, 4, 1])); // true
- Versi lambat membandingkan tiap pasangan: O(n²) waktu, tapi gak butuh memori tambahan.
- Versi cepat menyimpan angka yang sudah dilihat di
Set, kumpulan nilai tanpa kembar.hasrata-rata cuma butuh satu langkah, jadi totalnya O(n) waktu. Harganya O(n) memori, karenaSetbisa menyimpan semua angka.
Hash map (Map atau objek) memakai trik yang sama, misalnya untuk mencari dua angka yang jumlahnya pas: simpan yang sudah dilihat, lalu cek. Untuk n = 100.000, O(n²) berarti sekitar 10 miliar operasi (lebih dari satu menit), sedangkan O(n) cuma 100.000. Memoization dari materi DP juga sama: menyimpan hasil supaya gak dihitung ulang.
Kapan yang lambat justru tepat
Untuk 50 angka, dua loop bersarang cuma 2.500 operasi, selesai dalam sekejap. Jadi jawaban tebakan tadi: gak perlu. Versi yang simpel lebih gampang dibaca dan lebih kecil kemungkinan bug-nya.
Cara yang lebih lambat juga tepat kalau memorinya sempit: mengurutkan array lalu membandingkan angka yang bersebelahan butuh O(n log n) waktu, tapi gak perlu menyimpan salinan semua angka seperti Set.
Urutannya selalu begini: tulis dulu cara paling simpel yang benar, perkirakan operasinya dari n, dan baru cari cara yang lebih cepat kalau hitungannya gak muat.
Peta teknik di kategori ini
| Kalau soalnya tentang | Coba |
|---|---|
| mencari di data yang sudah urut | binary search |
| pasangan di array yang urut | two pointer |
| kelompok angka yang bersebelahan | sliding window |
| "sudah pernah lihat?" atau menghitung | hash map atau Set |
| hitungan kecil yang sama terus berulang | memoization dan DP |
| pilihan terbaik saat ini yang terbukti benar | greedy |
semua susunan, dengan n kecil |
backtracking |
| jalur terpendek dengan bobot | Dijkstra |
| urutan yang punya dependency | topological sort |
⚠️ Jebakan yang sering ketemu
- Langsung bikin versi rumit. Kode cepat yang salah gak ada gunanya. Mulai dari yang benar, baru percepat.
- Lupa memori. Cara O(n) yang menyimpan semua data bisa kehabisan memori kalau datanya miliaran.
- Lupa kasus pinggir. Array kosong, satu isi, semua isinya sama. Coba itu dulu sebelum bilang selesai.
- Menganggap hash map selalu satu langkah. Itu rata-ratanya. Di kasus terburuk bisa lebih lambat, walau jarang.
TL;DR: Tiap cara punya harga: waktu atau memori. Perkirakan dulu dari n dengan patokan sekitar 100 juta operasi per detik: 5.000 data masih aman untuk O(n²), 1.000.000 butuh O(n) atau O(n log n). Set dan hash map menukar memori O(n) dengan waktu: duplikat dan pasangan jadi O(n), bukan O(n²). Kalau datanya kecil atau memorinya sempit, cara yang simpel dan lebih lambat justru pilihan yang tepat.
