Diterbitkan pada

Notasi Big O dalam JavaScript

Penulis

Notasi Big O

Notasi Big O, yang secara kolektif disebut notasi Bachmann-Landau atau notasi asimtotik, adalah cara untuk menggambarkan performa sebuah algoritma. Notasi ini digunakan untuk menggambarkan skenario terburuk dari sebuah algoritma. Digunakan untuk membandingkan performa berbagai algoritma. Notasi ini menggambarkan implementasi algoritma dalam konteks ukuran input.

Notasi Big O mencirikan fungsi berdasarkan laju pertumbuhannya: tugas dengan laju pertumbuhan yang sama dianggap memiliki orde yang sama. Ini adalah notasi matematis yang menggambarkan perilaku pembatas fungsi ketika argumennya mendekati nilai tertentu atau tak terhingga. Notasi ini digunakan untuk mengklasifikasikan algoritma berdasarkan bagaimana waktu berjalan atau kebutuhan ruang mereka tumbuh seiring dengan bertambahnya ukuran input. Huruf O digunakan karena laju pertumbuhan suatu fungsi juga disebut ordenya.

Iterasi

Perulangan For

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

Kode di atas akan berjalan sebanyak n kali. Kompleksitas waktu kode ini adalah O(n).

Perulangan While

let i = 0
while (i < n) {
  console.log(i)
  i++
}

Kode di atas akan berjalan sebanyak n kali. Kompleksitas waktu kode ini adalah O(n).

Perulangan Do While

let i = 0
do {
  console.log(i)
  i++
} while (i < n)

Kode di atas akan berjalan sebanyak n kali. Kompleksitas waktu kode ini adalah O(n).

Rekursi

Faktorial

function factorial(n) {
  if (n === 0) {
    return 1
  }
  return n * factorial(n - 1)
}

Kode di atas akan berjalan sebanyak n kali. Kompleksitas waktu kode ini adalah O(n).

Fibonacci

function fibonacci(n) {
  if (n <= 1) {
    return n
  }
  return fibonacci(n - 1) + fibonacci(n - 2)
}

Kode di atas akan berjalan sebanyak n kali. Kompleksitas waktu kode ini adalah O(n).

Pencarian

Pencarian Linier

function linearSearch(arr, value) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === value) {
      return i
    }
  }
  return -1
}

Kode di atas akan berjalan sebanyak n kali. Kompleksitas waktu kode ini adalah O(n).

Pencarian Biner

function binarySearch(arr, value) {
  let start = 0
  let end = arr.length - 1
  let middle = Math.floor((start + end) / 2)
  while (arr[middle] !== value && start <= end) {
    if (value < arr[middle]) {
      end = middle - 1
    } else {
      start = middle + 1
    }
    middle = Math.floor((start + end) / 2)
  }
  if (arr[middle] === value) {
    return middle
  }
  return -1
}

Kode di atas akan berjalan sebanyak log(n) kali. Kompleksitas waktu kode ini adalah O(log(n)).

Pengurutan

Pengurutan Gelembung

function bubbleSort(arr) {
  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}

Kode di atas akan berjalan sebanyak n^2 kali. Kompleksitas waktu kode ini adalah O(n^2).

Pengurutan Seleksi

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let lowest = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) {
        lowest = j
      }
    }
    if (i !== lowest) {
      let temp = arr[i]
      arr[i] = arr[lowest]
      arr[lowest] = temp
    }
  }
  return arr
}

Kode di atas akan berjalan sebanyak n^2 kali. Kompleksitas waktu kode ini adalah O(n^2).

Pengurutan Penyisipan

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let currentVal = arr[i]
    for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      arr[j + 1] = arr[j]
    }
    arr[j + 1] = currentVal
  }
  return arr
}

Kode di atas akan berjalan sebanyak n^2 kali. Kompleksitas waktu kode ini adalah O(n^2).

Pengurutan Gabungan

function mergeSort(arr) {
  if (arr.length <= 1) return arr
  let mid = Math.floor(arr.length / 2)
  let left = mergeSort(arr.slice(0, mid))
  let right = mergeSort(arr.slice(mid))
  return merge(left, right)
}

function merge(left, right) {
  let results = []
  let i = 0
  let j = 0
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      results.push(left[i])
      i++
    } else {
      results.push(right[j])
      j++
    }
  }
  while (i < left.length) {
    results.push(left[i])
    i++
  }
  while (j < right.length) {
    results.push(right[j])
    j++
  }
  return results
}

Kode di atas akan berjalan sebanyak n log(n) kali. Kompleksitas waktu kode ini adalah O(n log(n)).

Pengurutan Cepat

function pivot(arr, start = 0, end = arr.length + 1) {
  let pivot = arr[start]
  let swapIdx = start
  function swap(array, i, j) {
    let temp = array[i]
    array[i] = array[j]
    array[j] = temp
  }
  for (let i = start + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      swapIdx++
      swap(arr, swapIdx, i)
    }
  }
  swap(arr, start, swapIdx)
  return swapIdx
}

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right)
    quickSort(arr, left, pivotIndex - 1)
    quickSort(arr, pivotIndex + 1, right)
  }
  return arr
}

Kode di atas akan berjalan sebanyak n log(n) kali. Kompleksitas waktu kode ini adalah O(n log(n)).

Tips untuk Big O

  • Operasi aritmatika adalah konstan
  • Penugasan variabel adalah konstan
  • Mengakses elemen dalam array (dengan indeks) atau objek (dengan kunci) adalah konstan
  • Dalam perulangan, kompleksitas adalah panjang perulangan dikalikan dengan kompleksitas apa pun yang terjadi di dalam perulangan

Sumber Daya

Diskusikan di Twitter

BAGIKAN