Big-O Notation

  Big-O Notation merupakan salah satu alat bantu yang bisa kita gunakan untuk mengukur efisiensi program yang kita buat untuk memecahkan suatu masalah.

Big-O notation digunakan untuk menghitung kompleksitas dari sebuah kode. Ada dua macam kompleksitas kode, yaitu:

1. Kompleksitas ruang/ space complexity berkaitan dengan memori yang digunakan.
2. Kompleksitas waktu/ time complexity berkaitan dengan waktu yang dibutuhkan untuk menjalankan program.

Notasi O besar atau yang biasa disebut dengan Big-O notation adalah cara untuk menganalisa waktu eksekusi sebuah algoritma pemrograman.

Di dalam program komputer, kita mengenal istilah Input - Proses - Output.

Notasi O besar adalah skenario terburuk (worst case) dari sebuah algoritma dan biasanya jumlah masukkan dilambangkan dengan notasi n.

Ada beberapa notasi yang seringkali muncul, yaitu O91), O(log n), O(n^2) atau O(n^n). Misalnya kita akan membuat program untuk mencari nilai terendah dari sebuah list. Maka berikut adalah kemungkinan yang dapat terjadi.

# 1. Pengulangan di dalam pengulangan memiliki nilai kompleksitas O(n^2). Dapat diilustrasikan pada potongan kode berikut:

for (let i = 0; i < List.length; i++) {
  for (let j = 0; j < List.length; j++) {
    // kode untuk membandingkan satu nilai dengan nilai lain
  }

Jika disimulasikan ketika jumlah data semakin banyak:

n	3	5	10	100
jumlah operasi	9	25	100	10000

Dari tabel diatas, antara 3 dan 5 maka perbedaan jumlah masukkannya hanya 2. Namun perbedaan jumlah operasi yang dijalankan sangat signifikan. Jumlah operasi yang dijalankan adalah jumlah masukkan pangkat 2 atau biasanya disebut dengan O(n^2).

Algoritma yang seperti ini sangat lambat dan tidak optimal.

# 2. Pengulangan dari sebuah set atau list memiliki nilai kompleksitas O(n). Dapat diilustrasikan pada potongan kode berikut:

for (let i = 0; i < List.length; i++) {
  // cari nilai paling kecil...
}

Pada ilustrasi kode diatas, maka pencarian nilai paling kecil hanya sejumlah nilai masukkan atau n, sehingga program yang kita butuhkan adalah O(n).

# 3. Hanya satu operasi, hal ini dapat terjadi jika list sudah terurut secara ascending, sehingga jumlah operasi adalah O(1).

Jika sebuah list sudah terurut ascending, maka untuk nilai terendah kita tinggal memanggil List[0] saja (data yang pertama). Tidak masalah sebanyak apapun isi array tersebut.

Secara umum berikut urutan dari notasi O besar diurutkan dari yang tercepat hingga yang terlambat.

<--- Super cepat ----------------------------------------- Super lambat --->

Nama:	Constant	Logaritmic	Linear	Quadratic	Exponential
Notasi:	O(1)	O(log n)	O(n)	O(n^2)	O(n^n)

Beberapa Contoh Notasi O Besar

1. Array.push()

push() merupakan sebuah metode untuk menambahkan item baru ke dalam sebuah array. Item yang ditambahkan akan berada diakhir array tersebut. Contoh :

const animals = ['ants', 'goats', 'cows'];
animals.push('fish');
console.log(animals); // ['ants', 'goats', 'cows', 'fish']

Notasi yang tepat untuk animals.push('fish'); adalah O(1) atau Constant. Karena metode push() tidak peduli dengan seberapa banyak jumlah item yang ada, artinya operasi yang berjalan tetap sama.

2. Array.pop()

pop() merupakan metode untuk mengambil item terakhir dari array sehingga jumlah item yang ada di array akan berkurang satu. Contoh

const plants = ['broccoli', 'cauliflower', 'cabbage', 'tomato'];
plants.pop();
console.log(plants); // ["broccoli", "cauliflower", "cabbage"]

Notasi untuk baris kode plants.pop(); adalah O(1) atau Constant. Sama dengan metode push(), metode pop() juga tidak mempermasalahkan jumlah item yang ada, artinya operasi yang berjalan tetap sama.

3. Array.unshift()

unshift() adalah sebuah metode untuk menambahkan satu atau beberapa item ke bagian awal dari sebuah array. Contoh kode:

const array1 = [1, 2, 3];
array1.unshift(4, 5);
console.log(array1); // [4, 5, 1, 2, 3]

Implementasi unshift() ini berbeda dengan dua metode sebelumnya.

function unshift(arr, newItem) {
  let newArr = [];
  newArr[0] = newItem;
  for (let i = 1; i < arr.length + 1; i++) {
    newArr[i] = arr[i - 1];
  }
  return newArr;
}

Pada implementasinya, kita harus mengubah indeks dari array karena kita akan menempatkan item baru di indeks ke-0. Secara otomatis, indeks akan bergeser sebanyak 1 langkah. Maka kita menggunakan pengulangan for dala operasi unshift() dengan nilai kompleksitasnya O(n).

Menghitung Total Kompleksitas Kode

Pembahasan diatas menunjukkan cara menghitung kompleksitas satu baris kode. Berikutnya kita akan menghitung total kompleksitas keseluruhan beberapa baris kode. Contoh kode:

for (let i = 0; i < 10; i++) {
  // O(n)
  for (let j = 0; j < 10; j++) {
    // O(n)
    console.log(i); // O(1)
    console.log(j); // O(1)
  }
}

kompleksitas potongan kode diatas dapat dihitung sebagai berikut:

untuk perulangan O(n) * O(n) = O(n^2)

untk perintah pada level yang sama O(1)+O(1) = O(2)

jika digabungkan menjadi O(n^2)O(2)

Namun  biasanya untuk jenis kode diatas cukup dilambangkan dengan 

O(n^2) karena O(2) tidak signifikan perbedaannya.

Berbeda dengan contoh kode berikut:

for (let i = 0; i < 10; i++) {
  // O(n)
  console.log(i);
}

for (let j = 0; j < 10; j++) {
  // O(n)
  console.log(j);
}

Kompleksitas potongan kode diatas dapat dihitung sebagai berikut:

O(n)+O(n) = O(2n)

Notasi O besar ini tidak hanya berlaku di bagian kode yang kita tulism namun juga berlaku di database. Jadi proses pengambilan data di database dengan Sintaksis SQL yang dapat dianggap sebagai proses perulangan, akan sangat tidak efektif jika di bagian algoritma kode kita kembali menggunakan perulangan. Jika hal tersebut terjadi maka nilai kompleksitas menjadi O(n^2)

Jika kita mengambil data dengan tabel yang tidak terindeks, maka prosesnya adalah "Sequential scan" yang melakukan perulangan setiap barisnya dan membandingkan dengan argumen query yang telah ditentukan.

Operasi sequential tersebut memiliki kompleksitas O(n), dimana dengan bertambahnya jumlah data, efisiensi semakin menurun.

Jika kita mengambil data dengan tabel yang sudah diindeks, maka secara otomatis kompleksitasnya akan menurun dan efisiensi akan naik, sehingga notasinya akan berubah dari O(n) menjadi O(log n). 

Daftar kompleksitas kode dari operasi-operasi yang umum kita jumpai:

Kompleksitas	Operasi
O(1)	Menjalankan sebuah perintah
O(n)	Mendapatkan sebuah item dari array, objek, atau variabel
O(log n)	Pengulangan yang berkurang setengahnya setiap iterasi
O(n^2)	Pengulangan dalam pengulangan
O(n^3)	Pengulangan dalam pengulangan dalam pengulangan

Sumber:

https://rizafahmi.com/