Notasi Big-O

Ketika kita memikirkan apakah barisan kode yang kita ciptakan sudah cukup cepat atau efisien dalam memecahkan masalah yang ingin kita pecahkan, maka kita butuh sebuah metodologi untuk menghitungnya. Nah, kali ini kita akan membahas salah satu alat yang dapat digunakan sebagai metodologi untuk menghitungnya, yaitu notasi O besar atau Big-O Notation. untuk lebih jelasnya simak penjelasan di bawah ini.

Apa itu Notasi Big-O?

Programmer yang baik akan menggunakan cara yang paling efektif dan efisien dalam menyelesaikan suatu permasalahan. Dan untuk bisa melakukan hal tersebut, kita harus bisa meminimalisir kompleksitas dari algoritma yang kita gunakan.

Kompleksitas suatu algoritma dibagi menjadi 2, yaitu Time Complexity dan Space Complexity. Namun, untuk saat ini kita hanya akan membahas mengenai Time Complexity dimana itu merupakan suatu cara analisa sederhana untuk mengetahui berapa lama waktu yang dibutuhkan untuk menjalankan suatu algoritma dengan input tertentu (n). Time complexity inilah yang populernya disebut Notasi Big-O.

Notasi O besar atau yang lazim disebut dengan Big-O Notation adalah cara untuk mengkonversi keseluruhan langkah-langkah suatu algoritma kedalam bentuk Aljabar, yaitu dengan menghiraukan konstanta yang lebih kecil dan koefisien yang tidak berdampak besar terhadap keseluruhan kompleksitas permasalahan yang diselesaikan oleh algoritma tersebut. Notasi Big-O ini merupakan skenario terburuk dari sebuah algoritma, dan biasanya terdapat notasi n yang merepresentasikan jumlah masukan. Notasi Big-O juga merupakan notasi yang paling terkenal dan paling banyak digunakan pada kalangan peneliti ilmu komputer.

Kegunaan Notasi Big-O

Notasi Big-O digunakan untuk mengukur tingkat kompleksitas suatu algoritma demi mengefisienkan algoritma itu sendiri. Notasi Big-O juga dapat merepresentasikan laju pertumbuhan (growth rate). Selain daripada itu, Notasi Big-O juga berguna untuk membandingkan beberapa algoritma untuk masalah yang sama demi menentukan yang terbaik. Contohnya seperti masalah pengurutan yang memiliki banyak metode/algoritma penyelesaian.

Selection sort, insertion sort -> T(n) = O(n²)
Quick sort -> T(n) = O (n log n)

Karena n log n < n² untuk n yang besar, maka algoritma quick sort lebih cepat (lebih baik) daripada algoritma selection sort ataupun insertion sort.

Jadi, nantinya kompleksitas algoritma akan dinilai dengan Notasi Big O yang terdiri dari seberapa lama algoritma itu berjalan (time complexity), dan seberapa banyak memori yang akan dipakai oleh algoritma itu (space complexity).

Dengan memahami Big-O Notation, kita akan lebih mudah dalam melihat mana algoritma yang lebih efisien yang bisa kita gunakan untuk menyelesaikan permasalahan yang sedang dihadapi.

Contoh Notasi Big-O

1. O(1) — Constant Time
Constant Time artinya banyaknya input yang diberikan kepada sebuah algoritma, tidak akan mempengaruhi waktu proses (runtime) dari algoritma tersebut.

2. O(log n) — Logarithmic Time
 Logarithmic Time artinya ketika kita memberikan input sebesar n terhadap sebuah fungsi, jumlah tahapan yang dilakukan oleh fungsi tersebut berkurang berdasarkan suatu faktor.

3. O(n) — Linear Time
Linear Time adalah ketika runtime dari fungsi kita berbanding lurus dengan jumlah input yang diberikan.

4. O(n²) — Quadratic Time
Quadratic Time adalah ketika runtime dari fungsi kita adalah sebesar n², dimana n adalah jumlah input dari fungsi tersebut.

5. (2ⁿ) —Exponential Time
Exponential Time biasanya digunakan dalam situasi dimana kita tidak terlalu tahu terhadap permasalahan yang dihadapi, sehingga mengharuskan kita mencoba setiap kombinasi dan permutasi dari semua kemungkinan.