Đăng ngày

Ký hiệu Big O trong JavaScript

Tác giả

Ký hiệu Big O

Ký hiệu Big O, còn được gọi là ký hiệu Bachmann-Landau hoặc ký hiệu tiệm cận, là một cách để mô tả hiệu suất của thuật toán. Nó được sử dụng để mô tả trường hợp xấu nhất của một thuật toán. Nó được sử dụng để so sánh hiệu suất của các thuật toán khác nhau. Nó mô tả việc triển khai một thuật toán theo kích thước đầu vào.

Ký hiệu Big O đặc trưng cho các hàm theo tốc độ tăng trưởng của chúng: các tác vụ có tốc độ tăng trưởng giống nhau được coi là cùng cấp. Nó là một ký hiệu toán học mô tả hành vi giới hạn của một hàm khi đối số có xu hướng tiến đến một giá trị cụ thể hoặc vô cực. Nó được sử dụng để phân loại các thuật toán theo cách thời gian chạy hoặc yêu cầu không gian của chúng phát triển khi kích thước đầu vào tăng lên. Chữ cái O được sử dụng bởi vì tốc độ tăng trưởng của một hàm cũng được gọi là bậc của nó.

Lặp

Vòng lặp For

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

Mã trên sẽ chạy n lần. Độ phức tạp thời gian của mã này là O(n).

Vòng lặp While

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

Mã trên sẽ chạy n lần. Độ phức tạp thời gian của mã này là O(n).

Vòng lặp Do while

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

Mã trên sẽ chạy n lần. Độ phức tạp thời gian của mã này là O(n).

Đệ quy

Giai thừa

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

Mã trên sẽ chạy n lần. Độ phức tạp thời gian của mã này là O(n).

Fibonacci

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

Mã trên sẽ chạy n lần. Độ phức tạp thời gian của mã này là O(n).

Tìm kiếm

Tìm kiếm tuyến tính

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

Mã trên sẽ chạy n lần. Độ phức tạp thời gian của mã này là O(n).

Tìm kiếm nhị phân

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
}

Mã trên sẽ chạy log(n) lần. Độ phức tạp thời gian của mã này là O(log(n)).

Sắp xếp

Sắp xếp nổi bọt

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
}

Mã trên sẽ chạy n^2 lần. Độ phức tạp thời gian của mã này là O(n^2).

Sắp xếp chọn

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
}

Mã trên sẽ chạy n^2 lần. Độ phức tạp thời gian của mã này là O(n^2).

Sắp xếp chèn

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
}

Mã trên sẽ chạy n^2 lần. Độ phức tạp thời gian của mã này là O(n^2).

Sắp xếp trộn

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
}

Mã trên sẽ chạy n log(n) lần. Độ phức tạp thời gian của mã này là O(n log(n)).

Sắp xếp nhanh

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
}

Mã trên sẽ chạy n log(n) lần. Độ phức tạp thời gian của mã này là O(n log(n)).

Mẹo cho Big O

  • Các phép toán số học là hằng số
  • Gán biến là hằng số
  • Truy cập các phần tử trong mảng (theo chỉ mục) hoặc đối tượng (theo khóa) là hằng số
  • Trong một vòng lặp, độ phức tạp là độ dài của vòng lặp nhân với độ phức tạp của bất kỳ điều gì xảy ra bên trong vòng lặp

Tài nguyên

Thảo luận trên Twitter

CHIA SẺ