Cara bermain Big-O Balapan
- Baca kode tiap pembalap di panel kanan (di ponsel, di atas). Kodenya sudah jadi. Tugasmu menilai mana yang lebih cepat.
- Pilih pembalap tercepat atau kelas Big-O dengan klik atau tombol panah. Di level urutan, susun pembalap dengan tombol naik dan turun.
- Tekan Cek jawaban atau Ctrl + Enter.
- Setelah benar, balapan diputar: n naik bertahap dan grafik menggambar jumlah operasi tiap pembalap. Geser slider untuk melihat n tertentu.
- Kalau buntu, buka Petunjuk. Level yang sudah selesai tetap tercentang di browser yang sama.
Yang kamu pelajari
- Level 1
O(1)
Langkahnya tetap, berapa pun n. Contohnya mengambil
arr[0]atauMap.get. - Level 1
O(n)
Langkahnya ikut n. n dua kali lipat, langkah dua kali lipat. Contohnya satu loop sepanjang array.
- Level 2
O(log n)
Data dibelah dua tiap langkah. n dua kali lipat, langkah cuma bertambah satu.
- Level 4
O(n²)
Loop di dalam loop. n dua kali lipat, langkah empat kali lipat.
- Level 5
Konstanta dibuang
Dua loop berurutan berarti 2n langkah, tetap ditulis O(n).
- Level 6
O(n log n)
Kelas sorting yang efisien seperti merge sort: log n tingkat belahan, n langkah per tingkat.
- Level 8
O(2ⁿ) dan memo
Rekursi yang bercabang dua berlipat tiap n bertambah 1. Menyimpan hasil (memo) menurunkannya jadi O(n).
Menang di n kecil belum tentu menang di n besar
Fungsi yang mengecek 50 aturan untuk tiap item butuh 50 × n langkah. Di n = 10 itu 500 langkah, kalah dari loop bersarang yang cuma 100.
Begitu n lewat 50, keadaannya berbalik. Di n = 2.000, 50 × n baru 100.000 langkah, sedangkan n × n sudah 4.000.000. Big-O membuang konstanta seperti 50 karena yang menentukan di data besar adalah cara langkahnya tumbuh.
Tanya jawab
Apakah harus daftar akun untuk bermain?
Tidak. Semua level bisa dimainkan tanpa akun. Kemajuanmu disimpan di browser yang kamu pakai, jadi akan hilang kalau data browser dihapus.
Dari mana jumlah operasi di grafik?
Dari menjalankan algoritmanya sungguhan di browser dengan penghitung. Satu operasi adalah satu perbandingan, satu putaran loop terdalam, atau satu panggilan fungsi. Jawaban tiap level juga dibuktikan dengan penghitungan yang sama lewat test otomatis.
Kenapa Fibonacci rekursif ditulis O(2ⁿ) padahal lipatannya sekitar 1,6?
Jumlah panggilannya tumbuh sekitar 1,6ⁿ. O(2ⁿ) adalah batas atas yang biasa dipakai karena tiap panggilan bercabang paling banyak dua. Keduanya sama-sama eksponensial.
Apakah Big-O mengukur waktu dalam detik?
Tidak. Big-O mengukur bagaimana jumlah langkah tumbuh saat n membesar. Waktu sebenarnya juga dipengaruhi mesin, bahasa, dan konstanta yang dibuang Big-O.
Kasus mana yang dihitung, terbaik atau terburuk?
Terburuk. Pencarian selalu mencari angka paling belakang, dan sorting diberi array yang urutannya terbalik.