Apa itu Big O Notation?
Bagi yang berpengalaman interview di perusahaan-perusahaan IT sebagai software engineer, pasti Anda tidak asing dengan Big O Notation. Big O Notation sederhananya adalah cara kita mengukur waktu yang dibutuhkan untuk menjalankan suatu algoritma, sehingga kita bisa tahu apakah algoritma yang digunakan efektif atau tidak.
Pengalaman saya pribadi setelah mengetahui konsep Big O Notation, saya menjadi paham bagaimana kualitas kode saya dan bagaimana cara membuatnya lebih berkualitas dan bisa bertahan dalam jangka waktu yang lama. Bahkan tidak hanya sekedar melihat dari sisi teknis kode, tetapi juga memudahkan saya mengambil keputusan dalam dunia nyata. Metode-metode yang ada selama ini dan dilakukan sehari-hari bisa kita ukur juga dengan teori ini. Oke dari pada penasaran, let’s go to the point!
O(1) — Constant
Cara saya memahami simbol diatas cukup simple, saya cukup menganggap O itu sebagai function pada kodingan saya, kemudian memiliki tugas yang konstan. Sehingga seluruh proses yang ada didalam fungsi tersebut hanya akan dijalankan secara konstan apapun parameternya. Contohnya:
function firstArray (array) {
return array[0]
}Contoh diatas menunjukkan bahwa banyak data array tidak akan pernah menghambat fungsi firstArray dalam menjalankan tugasnya, karena array yang dicari hanyalah index pertama atau 0.
Analogi:
Jika kita diberikan 2 buku yang tebalnya berbeda, buku 1 terdiri dari 300 halaman dan buku 2 terdiri dari 50 halaman. Ketika kita diminta untuk melihat sampulnya, maka waktu yang kita butuhkan untuk melihatnya adalah sama baik buku 1 maupun 2. Karena, sampul buku akan selalu terlihat duluan dibanding isinya.
O(n) — Linear
Sederhananya adalah semakin banyak data yang diterima maka semakin lama pula prosesnya selesai. Ketika kita memiliki 5 data di dalam sebuah array dan kita melakukan perulangan berdasarkan array tersebut, maka proses yang terjadi didalamnya akan sama dengan banyaknya data array.
function alertIndex(array) {
for (let i = 0; i < array.length; i++) {
alert(i);
}
}Perulangan diatas menunjukkan bahwa fungsi alert akan dijalankan sebanyak panjangnya data array. Sehingga semakin banyak data yang kita miliki dalam array tersebut, maka semakin lama pula fungsi diatas menyelesaikan tugasnya.
Analogi:
Contoh dalam kegiatan sehari-hari ialah membaca buku. Semakin tebal bukunya, semakin lama pula kita menamatkan bukunya.
O(n²) — Quadratic
Yang biasa buat perulangan dalam perulangan, nah itu contoh untuk O(n²). Maksudnya, setiap n berpotensi memiliki proses O(n) sehingga mengakibatkan proses tidak efektif. Namun, bukan berarti menggunakan logika seperti ini dilarang. Hanya saja sangat tidak dianjurkan menggunakan logika perulangan bercabang untuk data yang bisa berkembang atau bertambah. Hal ini bisa dilakukan ketika data yang akan diproses bersifat statis dan sedikit.
Analogi:
Contoh dalam kehidupan sehari-hari adalah mengurutkan jualan misal berdasarkan harga. Prosesnya berarti kita perlu mengetahui semua harga barang, kemudian kita mengambil satu barang sebagai patokan dan melihat ke semua barang apakah ada yang lebih murah. Jika ada, maka barang tersebut akan menjadi patokan baru. Aktifitas ini akan terus berulang sampai semua barang terurut.
O(log n) — Logarithmic
Sebelumnya apa itu logarithmic atau logaritma? Hehe saya juga puyeng gan awalnya 😅. Nostalgia pelajaran Matematika SMA. Intinya menurut saya O(log n) adalah memecah nilai n dengan menggunakan suatu faktor. Sehingga kita bisa melakukan O(n) dengan pecahan dari n yang memenuhi kriteria.
Kali ini saya akan mencoba memberikan dua analogi dalam kehidupan kita sehari-hari agar mudah dipahami.
Analogi 1 — Mencari Halaman Buku
Ketika kita mencari suatu halaman dalam sebuah buku, sebenarnya kita secara tidak langsung telah menggunakan metode O(log n). Contoh kasus saya memiliki buku 300 lembar, kemudian saya ingin mencari halaman 120. Jika kita menggunakan metode O(n), maka step yang kita perlukan untuk mencapai halaman 120 adalah dengan membuka buku dari halaman 1 sampai halaman 120. Berarti step yang dibutuhkan adalah 120.
Berbeda dengan kebiasaan kita, hal yang pertama yang biasa dilakukan adalah membuka halaman secara acak menurut perkiraan dan anggaplah sekarang kita membuka halaman 140. Dari sini kita sudah memecah buku menjadi 2 yaitu halaman <140 dan halaman >140. Karena yang kita cari adalah 120, berarti halaman tersebut berada pada pecahan <140. Jarak antara 120 dan 140 adalah 20 sehingga step yang dibutuhkan untuk algoritma ini adalah 21.
- Buka acak = 1 step
- Cari 120 dari halaman 140 = 20 step
- Total step = 21 step
Analogi 2 — Mencari Nomor Telpon di Buku Telpon
Buku telpon umumnya memiliki klasifikasi abjad untuk mempermudah pencarian. Hal ini juga dikatakan O(log n) karena prosesnya memecah n dengan faktor abjad, sehingga kita dapat memfokuskan O(n) pada pecahan yang memenuhi kriteria pencarian saja.
Catatan Penting: Dari analogi yang saya paparkan soal O(log n), ini menandakan indexing pada suatu data akan sangat baik jika memungkinkan kita melakukan klasifikasi dengan index tersebut. Itulah sebabnya database memiliki fitur index auto increment, atau index menggunakan timestamp seperti yang dilakukan mongodb. Karena kita bisa melakukan pencarian berdasarkan faktor urutan terkecil dan terbesar berdasarkan angka, juga pencarian berdasarkan waktu. CMIIW
Kesimpulan
O(1) = Ez 😍
O(log n) = Awesome 😘
O(n) = Ok fine 😉
O(n²) = Fucek 😡Itulah mungkin penjelasan sederhana untuk Big O Notation yang bisa saya tuliskan. Correct me If I’m wrong. Semoga bermanfaat, see you… thanks.
