Analisis kompleksitas artinya menebak seberapa cepat kode melambat waktu datanya membesar, dan hasilnya ditulis dengan Big-O, dengan n sebagai banyaknya data. O(1) artinya waktunya tetap berapa pun datanya, O(n) artinya datanya dua kali lipat, waktunya kira-kira dua kali lipat. Di pelajaran penutup ini ada tabel ringkas biaya tiap struktur data, lalu cara membaca function-mu sendiri untuk menebak Big-O-nya.
🧪 Tebakan cepat:
for (let i = 1; i < n; i *= 2)dengan n = 1.000 jalan berapa putaran: sekitar 10, 500, atau 1.000? Tebak dulu, jawabannya ada di bagian "Dibagi dua tiap putaran: O(log n)".
Tabel ringkas: biaya tiap operasi
const n = 1000;
const arr = Array.from({ length: n }, (_, i) => i); // 0 sampai 999
const set = new Set(arr);
console.log(arr[n - 1]); // 999, O(1): langsung ke index-nya
console.log(arr.includes(-1)); // false, O(n): 1.000 data dicek satu per satu
console.log(set.has(-1)); // false, O(1) rata-rata
Datanya sama, tapi biaya mencarinya beda jauh. Ini biaya tiap operasi untuk tiap struktur:
| Struktur | Akses (index) | Cari | Sisip | Hapus |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) |
| Queue | O(n) | O(n) | O(1) | O(1) |
| Linked list | O(n) | O(n) | O(1) | O(1) |
| Hash map | gak ada | O(1)* | O(1)* | O(1)* |
| BST | gak ada | O(log n)* | O(log n)* | O(log n)* |
| Heap | gak ada | O(n) | O(log n) | O(log n) |
- Tanda * artinya rata-rata. Kasus terburuknya O(n): hash map yang key-nya banyak bertabrakan, atau BST yang gak seimbang.
- Sisip dan hapus di array O(n) karena isinya harus digeser. Di ujung (
push,pop) cuma O(1). - Sisip dan hapus O(1) di linked list berlaku di node yang sudah kamu pegang, misalnya di head.
Seberapa besar bedanya untuk n = 1.000: O(1) satu langkah, O(log n) sekitar 10, O(n) 1.000, O(n log n) sekitar 10.000, dan O(n²) sejuta.
Satu loop: O(n)
Untuk function-mu sendiri, tanyakan: kalau n bertambah, berapa kali baris di dalam loop dijalankan?
function total(arr) {
let sum = 0;
for (const x of arr) {
sum += x;
}
return sum;
}
console.log(total([5, 10, 15])); // 30
Loop-nya jalan sekali untuk tiap isi: n isi, n putaran. Isinya dua kali lipat, putarannya dua kali lipat: O(n). Baris di luar loop (let sum = 0, return) cuma jalan sekali, jadi gak dihitung.
Loop di dalam loop: O(n²)
function hitungPasangan(arr) {
let pasangan = 0;
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
pasangan++;
}
}
return pasangan;
}
console.log(hitungPasangan([1, 2, 3, 4])); // 6
Untuk tiap i, loop dalam jalan sampai akhir array. Dengan 4 isi: 3 + 2 + 1 = 6 putaran. Dengan 1.000 isi: 499.500, kira-kira n × n / 2. Big-O membuang angka pengali seperti "/ 2", jadi hasilnya O(n²): isinya dua kali lipat, waktunya kira-kira empat kali lipat. Loop dalam yang mulai dari i atau dari 0 sama-sama O(n²).
Dibagi dua tiap putaran: O(log n)
function langkahBagiDua(n) {
let langkah = 0;
for (let i = 1; i < n; i *= 2) {
langkah++;
}
return langkah;
}
console.log(langkahBagiDua(8)); // 3
console.log(langkahBagiDua(1000)); // 10
i dikali dua tiap putaran: 1, 2, 4, 8, ... Untuk n = 8, i bernilai 1, 2, 4, lalu berhenti di 8: 3 putaran. Untuk n = 1.000 cuma 10 putaran, dan untuk sejuta cuma 20. Itu jawaban tebakan tadi. Kalau sisa kerjanya dikali dua atau dibagi dua tiap putaran, seperti binary search, Big-O-nya O(log n).
Menggabungkan: jumlah, kali, buang konstanta
- Berurutan: ambil yang terbesar. Satu loop selesai, lalu loop lain: n + n = 2n, tetap O(n). Loop O(n) lalu loop bersarang O(n²): O(n²).
- Bersarang: kalikan. Loop n di dalam loop n: n × n = O(n²).
- Method bawaan juga dihitung.
includes,indexOf, danshiftbekerja satu per satu, O(n). Satuincludesdi dalam loop sama dengan loop di dalam loop: O(n²). - Buang angka tetap. 3n jadi O(n), n² / 2 jadi O(n²). Loop yang selalu jalan 10 kali, berapa pun n, itu O(1).
⚠️ Jebakan yang sering ketemu
- Membaca O(1) sebagai jaminan.* Itu rata-rata. Hash map dan BST tetap bisa O(n) di kasus terburuk.
- Menghitung dua loop berurutan sebagai O(n²). Yang O(n²) cuma loop yang ada di dalam loop lain.
- Big-O dianggap waktu pasti. Big-O bicara soal data yang besar. Untuk puluhan data, kode O(n²) yang sederhana bisa lebih cepat dari kode O(n log n) yang ribet.
TL;DR: Big-O menghitung berapa kali kerjanya diulang waktu n membesar. Satu loop atas n data: O(n). Loop di dalam loop: O(n²), walau loop dalamnya mulai dari i. Dikali atau dibagi dua tiap putaran: O(log n), sekitar 10 langkah untuk 1.000 data. Loop berurutan dijumlah lalu ambil yang terbesar, loop bersarang dikali, angka tetap dibuang, dan method seperti includes di dalam loop ikut dihitung. Array: akses O(1), cari O(n). Hash map dan Set: cari O(1) rata-rata. BST seimbang: O(log n). Heap: sisip dan hapus O(log n).
