Mengenal Big O notation dalam pemrograman

Semua pemrogram pasti ingin semua kode yang ia tulis menghasilkan kode yang efisien. Dari sini muncul pertanyaan, bagaimana kita menentukan mana kode yang efisien dan mana yang bukan ? untuk mengetahuinya kita bisa memakai konsep Big O notation.

Jadi apa itu Big O notation ?

Big O notation adalah sebuah notasi matematis, untuk mengkomunikasikan seberapa efisien suatu algoritma bereaksi terhadapat jumlah data yang perlu diproses.

Efisiensi dalam hal ini adalah efisiensi secara umum, karena bisa jadi 2 algoritma mempunya notasi yang sama, tetapi ketika dibenchmark hasilnya cukup berbeda, hal ini bisa jadi karena beberapa kasus semisal compiler/intrepeter dari bahasa yang kita pakai sudah mengoptimasi secara otomatis.

Efisiensi suatu algoritma bisa dilihat dari 2 sisi.

1. Time Complexity

Yaitu berapa waktu/langkah yang dibutuhkan untuk menyelesaikan suatu tugas.

2. Space Complexity

Yaitu berapa memory yang dibutukan untuk menyelesaikan tugas. ada kalanya suatu algoritma lebih cepat dalam menyelesaikan suatu tugas, tetapi membutuhkan memory lebih banyak.

Dari 2 sisi diatas, ketika kita berbicara tentang big o notation, umumnya yang dibahas adalah tentang Time Complexity, maka dari itu mari kita bahas beberapa notasi big O melalui kacamata Time Complexity.

1. O(1) - Constant time

Contoh function yang mempunya notation O(1)

let data = [0, 2, 3, 4, 5, 7, 8];
function getFirstData(data) {
  if (data.length < 1) {
    throw "not enough";
  }
  let first = data[0];
  return first
}
 
console.log(getFirstData(data));

didalam function getFirstData() kita bisa mengetahui secara umum diperlukan minimal 2 langkah untuk menjalankan algoritma didalam function tersebut atau bisa kita notasikan O(2). Function ini akan tetap konstan berapapun jumlah input yang diberikan, apakah itu array berisi 10 data atau 100rb data, maka dari itu notasi O(2) bisa kita sederhakan menjadi O(1).

3. O(n) - Linear time

berikut contoh kodenya

let data = ["dog", "bird", "rabbit", "cat"];
 
function findCat(data) {
  for (const item of data) {
    if (item === "cat") {
      return item;
    }
  }
 
  return null;
}
console.log(findCat(data));

pada function findCat() ini kita bisa mengasumsikan, setidaknya membutuhkan 1-4 iterasi untuk mencari element yang berisi string "cat", jika data yang berisi "cat" ada diindex pertama maka cukup 1 kali iterasi, jika "cat" berada diakhir array, maka akan dieksusi sebesar 4 kali iterasi. singkatnya notasinya bisa dari 0(1) sampai dengan O(4), dari sini perlu dipahami bahwa notasi big O akan selalu ditulis dalam bentuk worst case scenarionya yakni O(4) atau bisa ditulis O(n), dimana n adalah jumlah data.

3. O(log n) — Logarithmic Time

function binarySearch(data, x) {
  let start = 0;
  let end = data.length - 1;
 
  while (start <= end) {
    let middle = Math.floor((start + end) / 2);
    console.log(middle)
    if (data[middle] === x) {
      return true;
    } else if (data[middle] < x) {
      start = middle + 1;
    } else {
      end = middle - 1;
    }
  }
 
  return false;
}
 
let sortedData = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(binarySearch(sortedData, 1));

Salah satu contoh implementasi O(log n) adalah dengan binary search, function binarySearch() akan memotong array menjadi 2 bagian disetiap iterasi perulangan dan hanya akan melanjutkan pencarian disisi yang terdapat data yang dicari, hal ini akan membuat pencarian data menjadi lebih cepat karena program tidak perlu melakukan iterasi disemua element array layaknya algoritma bersifat linear / O(1).

namum yang perlu diperhatikan dalam binary search ini yaitu algoritma akan berjalan dengan sesuai, jika data yang dimasukkan sudah tersorting dengan baik.

4. O(n²) — Quadratic Time

let data = [5, 4, 3, 2, 1, 10, 9, 8, 7, 6];
 
function bubbleSort(data) {
  let len = data.length;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      if (data[j] > data[j + 1]) {
        let tmp = data[j];
        data[j] = data[j + 1];
        data[j + 1] = tmp;
      }
    }
  }
  return data;
}
console.log(bubbleSort(data));

Operasi yang dibutuhkan untuk mensorting dengan bubbleSort untuk 10 element yaitu 100 langkah, atau n².

5. O(2^n) — Exponential Time

Salah santuh contoh ketika perlu membuat semua kombinasi dari suatu topping makanan, maka langkah yang perlu dilakukan akan meningkat secara exponential sesuai jumlah topping yang ada.

0 toppings: 1 combination (no toppings at all)
1 toppings: 2 combinations (none, a)
2 toppings: 4 combinations (none, a, b, ab)
3 toppings: 8 combinations (none, a, b, c, ab, ac, bc, abc)
...
...
10 toppings: 1,024 combinations
20 toppings: 1,048,576 combinations

Kesimpulan

Memahami konsep Big O notation ini akan sangat bermanfaat terutama untuk membentuk mental model, sehingga ketika menulis kode, kita bisa menebak secara umum, bagaimana sebuah algoritma akan berjalan efisien atau tidak, sesuai jumlah data yang akan diproses kemudian hari.