1. Apa itu Notasi Big-O?
Kita tidak bisa mengukur efisiensi kode hanya dengan stopwatch (detik/milidetik) karena kecepatan komputer setiap orang berbeda (laptop gaming vs server lawas). Notasi Big-O mengukur bagaimana **jumlah operasi (Time Complexity)** atau **konsumsi memori (Space Complexity)** bertumbuh seiring membesarnya ukuran data input (N).
Tingkatan Kompleksitas Big-O dari Tercepat ke Terlambat
1. **O(1) - Constant Time**: Kecepatan instan, tidak peduli berapa pun ukuran N (misal: mengakses `arr[0]` atau mengambil data by Key di Hash Map).
2. **O(log N) - Logarithmic Time**: Sangat cepat! Jumlah langkah hanya bertambah sedikit saat N berlipat ganda (misal: Binary Search).
3. **O(N) - Linear Time**: Waktu eksekusi sebanding lurus dengan jumlah data (misal: satu for loop melintasi array).
4. **O(N log N)**: Kompleksitas algoritma pengurutan modern terbaik (Merge Sort, Timsort).
5. **O(N^2) - Quadratic Time**: Lambat! Berbahaya untuk data besar (misal: nested for loop di dalam for loop / Bubble Sort).
Perbandingan Kode O(1), O(N), dan O(N^2)
javascript
| 1 | // 1. O(1) - Konstan |
| 2 | function ambilPertama(arr) { |
| 3 | return arr[0]; |
| 4 | } |
| 5 | |
| 6 | // 2. O(N) - Linier (1 loop) |
| 7 | function cetakSemua(arr) { |
| 8 | for (let i = 0; i < arr.length; i++) { |
| 9 | console.log(arr[i]); |
| 10 | } |
| 11 | } |
| 12 | |
| 13 | // 3. O(N^2) - Kuadratik (Nested loop: Jika N=1000, operasi = 1.000.000!) |
| 14 | function cetakSemuaPasangan(arr) { |
| 15 | for (let i = 0; i < arr.length; i++) { |
| 16 | for (let j = 0; j < arr.length; j++) { |
| 17 | console.log(arr[i], arr[j]); |
| 18 | } |
| 19 | } |
| 20 | } |
Kuis Pemahaman
+10 XP
Jika fungsi memiliki dua perulangan bersarang (nested loops) di mana masing-masing loop berputar sebanyak N kali, berapa Time Complexity fungsi tersebut?