Nai-publish noong

Big O Notation sa JavaScript

Mga May-akda

Ang Big O Notation

Ang Big O Notation, na tinatawag ding Bachmann-Landau notation o asymptotic notation, ay isang paraan upang ilarawan ang pagganap ng isang algorithm. Ginagamit ito upang ilarawan ang pinakamasamang sitwasyon ng isang algorithm. Ginagamit ito upang ihambing ang pagganap ng iba't ibang mga algorithm. Inilalarawan nito ang pagpapatupad ng isang algorithm sa mga tuntunin ng laki ng input.

Inilalarawan ng Big O notation ang mga function ayon sa kanilang mga rate ng paglaki: ang mga gawain na may parehong rate ng paglaki ay itinuturing na nasa parehong order. Ito ay isang mathematical notation na naglalarawan ng limitadong pag-uugali ng isang function kapag ang argument ay may posibilidad na lumapit sa isang partikular na halaga o infinity. Ginagamit ito upang i-classify ang mga algorithm ayon sa kung paano lumalaki ang kanilang oras ng pagpapatakbo o mga kinakailangan sa espasyo habang lumalaki ang laki ng input. Ang titik O ay ginagamit dahil ang rate ng paglaki ng isang function ay tinatawag ding order nito.

Pag-ulit

For loop

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

Ang code sa itaas ay tatakbo ng n beses. Ang time complexity ng code na ito ay O(n).

While loop

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

Ang code sa itaas ay tatakbo ng n beses. Ang time complexity ng code na ito ay O(n).

Do while loop

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

Ang code sa itaas ay tatakbo ng n beses. Ang time complexity ng code na ito ay O(n).

Recursion

Factorial

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

Ang code sa itaas ay tatakbo ng n beses. Ang time complexity ng code na ito ay O(n).

Fibonacci

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

Ang code sa itaas ay tatakbo ng n beses. Ang time complexity ng code na ito ay O(n).

Paghahanap

Linear search

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

Ang code sa itaas ay tatakbo ng n beses. Ang time complexity ng code na ito ay O(n).

Binary search

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
}

Ang code sa itaas ay tatakbo ng log(n) beses. Ang time complexity ng code na ito ay O(log(n)).

Pag-uuri

Bubble sort

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
}

Ang code sa itaas ay tatakbo ng n^2 beses. Ang time complexity ng code na ito ay O(n^2).

Selection sort

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
}

Ang code sa itaas ay tatakbo ng n^2 beses. Ang time complexity ng code na ito ay O(n^2).

Insertion sort

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
}

Ang code sa itaas ay tatakbo ng n^2 beses. Ang time complexity ng code na ito ay O(n^2).

Merge sort

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
}

Ang code sa itaas ay tatakbo ng n log(n) beses. Ang time complexity ng code na ito ay O(n log(n)).

Quick sort

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
}

Ang code sa itaas ay tatakbo ng n log(n) beses. Ang time complexity ng code na ito ay O(n log(n)).

Mga Tip para sa Big O

  • Ang mga arithmetic operation ay pare-pareho
  • Ang pagtatalaga ng variable ay pare-pareho
  • Ang pag-access ng mga elemento sa isang array (sa pamamagitan ng index) o object (sa pamamagitan ng key) ay pare-pareho
  • Sa isang loop, ang complexity ay ang haba ng loop na pinarami ng complexity ng anumang nangyayari sa loob ng loop

Mga Sanggunian

Talakayin sa Twitter

IBAHAGI