Tất tần tật về Notation Big O: Tối ưu hóa mã nguồn

Giới thiệu

Bạn có bao giờ tự hỏi tại sao mã của bạn chậm lại khi thêm dữ liệu? Hay tại sao một số thuật toán nhanh hơn những thuật toán khác, ngay cả khi chúng thực hiện cùng một nhiệm vụ? Câu trả lời thường ẩn chứa trong một khái niệm gọi là Notation Big O.

Trong bài viết này, chúng ta sẽ phân tích Notation Big O một cách đơn giản nhất có thể. Bạn sẽ hiểu nó là gì, tại sao nó quan trọng và cách nhận biết nó trong mã của bạn. Không cần bằng cấp toán học!

Notation Big O là gì?

Notation Big O là cách mô tả cách thời gian (hoặc bộ nhớ) mà mã của bạn cần tăng lên khi đầu vào lớn hơn. Thay vì đo thời gian chạy của một hàm, Big O giúp bạn dự đoán hành vi của mã khi xử lý dữ liệu nhỏ, trung bình hoặc lớn.

Hãy xem nó như một đồng hồ đo tốc độ cho hiệu suất của mã bạn.

Tại sao bạn nên quan tâm?

• Nhà tuyển dụng rất yêu thích. Big O là một chủ đề yêu thích trong các cuộc phỏng vấn lập trình, đặc biệt là với các công ty lớn như Google, Amazon và Meta.
• Giúp bạn viết mã tốt hơn. Hiểu Big O cho phép bạn chọn thuật toán phù hợp cho công việc.
• Tiết kiệm đau đầu. Bạn sẽ tránh được các tình huống chậm trễ và lỗi chỉ xuất hiện với dữ liệu lớn.

Bốn loại Big O phổ biến nhất

Hãy cùng xem bốn loại Big O mà bạn thường gặp:

1. Thời gian không đổi – O(1)

Dù đầu vào của bạn lớn bao nhiêu, mã luôn mất cùng một lượng thời gian.

function getFirstItem(arr) {
  return arr[0];
}

Dù arr có 10 mục hay 10 triệu mục, hàm này luôn nhanh. Đó là O(1).

2. Thời gian tuyến tính – O(n)

Thời gian tăng lên theo tỷ lệ với kích thước đầu vào.

function printAll(arr) {
  for (let item of arr) {
    console.log(item);
  }
}

Nếu bạn gấp đôi số lượng mục, hàm sẽ mất gấp đôi thời gian. Đó là O(n).

3. Thời gian bình phương – O(n^2)

Thời gian tăng lên với bình phương kích thước đầu vào. Điều này thường xảy ra với các vòng lặp lồng ghép.

function printPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}

Nếu bạn có 10 mục, nó in ra 100 cặp. Với 100 mục, nó in ra 10.000 cặp! Đó là O(n^2).

4. Thời gian logarithmic – O(log n)

Thời gian tăng lên chậm, ngay cả khi đầu vào lớn. Điều này xảy ra khi bạn có thể cắt giảm vấn đề mỗi bước, như trong tìm kiếm nhị phân.

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Với 1.000.000 mục, tìm kiếm nhị phân chỉ cần khoảng 20 bước để tìm một thứ gì đó. Đó là O(log n).

Hình dung Big O

Hãy tưởng tượng bạn đang chạy một cuộc đua. O(1) giống như chạy nước rút một khoảng ngắn—luôn nhanh. O(n) giống như chạy bộ trên một đường dài. O(n^2) giống như chạy vòng trong vòng—mệt mỏi! O(log n) giống như dịch chuyển gần hơn đến vạch đích với mỗi bước.

Ví dụ mã trong thực tế

Tìm một mục trong danh sách

function contains(arr, target) {
  for (let item of arr) {
    if (item === target) return true;
  }
  return false;
}

Điều này là O(n) vì bạn có thể phải kiểm tra mọi mục.

Nhưng nếu bạn sử dụng một Set:

const items = new Set(["apple", "banana", "cherry"]);
items.has("banana"); // O(1)

Tìm kiếm trong Set là O(1)!

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

Sắp xếp nổi bọt là một ví dụ cổ điển của O(n^2):

function bubbleSort(arr) {
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
  } while (swapped);
  return arr;
}

Lưu trữ kết quả

Đôi khi bạn có thể tăng tốc độ bằng cách nhớ các kết quả trước đó (caching):

const cache = new Map();
function factorial(n) {
  if (cache.has(n)) return cache.get(n);
  if (n === 0) return 1;
  const result = n * factorial(n - 1);
  cache.set(n, result);
  return result;
}

Kết luận

Notation Big O giúp bạn viết mã vẫn nhanh—ngay cả khi dữ liệu của bạn phát triển. Dù bạn đang chuẩn bị cho các cuộc phỏng vấn hay chỉ muốn trở thành một lập trình viên tốt hơn, hiểu Big O là một siêu năng lực.

Nếu bạn thấy hướng dẫn này hữu ích, hãy chia sẻ với bạn bè hoặc đánh dấu nó cho phiên chuẩn bị phỏng vấn tiếp theo của bạn!