Diterbitkan pada

Nombor Terbesar dalam JavaScript dalam O

Penulis

Notasi Big O

Notasi Big O, secara kolektif dipanggil notasi Bachmann-Landau atau notasi asimtotik, ialah cara untuk menggambarkan prestasi suatu algoritma. Ia digunakan untuk menerangkan senario kes terburuk bagi suatu algoritma. Ia digunakan untuk membandingkan prestasi algoritma yang berbeza. Ia menerangkan pelaksanaan suatu algoritma dari segi saiz input.

Notasi Big O mencirikan fungsi mengikut kadar pertumbuhannya: tugas dengan kadar pertumbuhan yang sama dianggap sebagai urutan yang sama. Ia merupakan notasi matematik yang menerangkan tingkah laku had suatu fungsi apabila hujah cenderung ke arah nilai tertentu atau infiniti. Ia digunakan untuk mengelaskan algoritma mengikut bagaimana masa berjalan atau keperluan ruangnya tumbuh apabila saiz input tumbuh. Huruf O digunakan kerana kadar pertumbuhan suatu fungsi juga dipanggil susunannya.

Pengulangan

Gelung For

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

Kod di atas akan berjalan n kali. Kerumitan masa kod ini ialah O(n).

Gelung While

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

Kod di atas akan berjalan n kali. Kerumitan masa kod ini ialah O(n).

Gelung Do While

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

Kod di atas akan berjalan n kali. Kerumitan masa kod ini ialah O(n).

Rekursi

Faktorial

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

Kod di atas akan berjalan n kali. Kerumitan masa kod ini ialah O(n).

Fibonacci

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

Kod di atas akan berjalan n kali. Kerumitan masa kod ini ialah O(n).

Pencarian

Pencarian Linear

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

Kod di atas akan berjalan n kali. Kerumitan masa kod ini ialah 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
}

Kod di atas akan berjalan log(n) kali. Kerumitan masa kod ini ialah O(log(n)).

Pengaturan

Pengaturan 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
}

Kod di atas akan berjalan n^2 kali. Kerumitan masa kod ini ialah O(n^2).

Pengaturan Pemilihan

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
}

Kod di atas akan berjalan n^2 kali. Kerumitan masa kod ini ialah O(n^2).

Pengaturan 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
}

Kod di atas akan berjalan n^2 kali. Kerumitan masa kod ini ialah O(n^2).

Pengaturan 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
}

Kod di atas akan berjalan n log(n) kali. Kerumitan masa kod ini ialah O(n log(n)).

Pengaturan 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
}

Kod di atas akan berjalan n log(n) kali. Kerumitan masa kod ini ialah O(n log(n)).

Petua untuk Big O

  • Operasi aritmetik adalah tetap
  • Peruntukan pembolehubah adalah tetap
  • Mengakses elemen dalam suatu tatasusunan (mengikut indeks) atau objek (mengikut kunci) adalah tetap
  • Dalam suatu gelung, kerumitannya ialah panjang gelung didarab dengan kerumitan apa sahaja yang berlaku di dalam gelung

Sumber

Bincangkan di Twitter

KONGSI