Big O notation: đo tốc độ thuật toán như thế nào?

Big O là gì?

Big O mô tả tốc độ tăng trưởng của thời gian chạy khi dữ liệu lớn lên. Không đo “chạy bao nhiêu giây”, mà đo “khi dữ liệu gấp đôi, thời gian tăng bao nhiêu lần?”.

Nhận diện Big O từ code

// File: bigo.js
// O(1) — Hằng số: không phụ thuộc kích thước mảng
function getFirst(arr) {
  return arr[0]
}

// O(n) — Tuyến tính: duyệt mảng 1 lần
function findMax(arr) {
  let max = arr[0]
  for (const num of arr) {
    if (num > max) max = num
  }
  return max
}

// O(n²) — Bình phương: 2 vòng lặp lồng nhau
function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true
    }
  }
  return false
}

// O(n) — dùng Set thay vì 2 vòng lặp → nhanh hơn!
function hasDuplicateFast(arr) {
  const seen = new Set()
  for (const num of arr) {
    if (seen.has(num)) return true
    seen.add(num)
  }
  return false
}

Binary Search: sức mạnh của O(log n)

Tìm số trong mảng đã sắp xếp: thay vì duyệt từ đầu (O(n)), chia đôi mỗi bước. Mảng 1 triệu phần tử? Chỉ cần ~20 bước thay vì 1 triệu bước.

// File: binary-search.js
// Binary Search: tìm trong mảng ĐÃ SẮP XẾP
function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1

  while (left <= right) {
    const mid = Math.floor((left + right) / 2)

    if (arr[mid] === target) return mid      // Tìm thấy!
    if (arr[mid] < target) left = mid + 1    // Target ở nửa phải
    else right = mid - 1                     // Target ở nửa trái
  }

  return -1 // Không tìm thấy
}

const sorted = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
console.log(binarySearch(sorted, 23)) // 5 (index)

• Giải thích Big O bằng ví dụ thực tế
• Nhận diện O(1), O(n), O(n²), O(log n) từ code
• Triển khai Binary Search
• Biết vì sao O(n²) chậm hơn O(n log n) khi n lớn