Big-O trong lập trình: học bằng cách nhìn số lần chương trình phải làm việc

Mô tả SEO: Bài giảng dễ hiểu về Big-O, độ phức tạp thuật toán, O(1), O(log n), O(n), O(n log n), O(n²), cách đọc vòng lặp, cách tối ưu code và bài tập thực hành.

Từ khóa: Big-O, độ phức tạp thuật toán, algorithm complexity, time complexity, space complexity, học lập trình, tối ưu code.

Mục tiêu bài học: Sau bài này, bạn phải tự đọc được một đoạn code đơn giản và trả lời được: khi dữ liệu tăng lên, đoạn code đó chậm đi theo kiểu nào.

Nguồn ảnh: biểu đồ PNG tự tạo cho bài viết này, dựa trên khái niệm ký hiệu tiệm cận và tốc độ tăng hàm trong MIT, Khan Academy và Princeton. Không sử dụng SVG.

1. Big-O là gì, nói theo kiểu dễ hiểu?

Big-O là cách mô tả mức độ tăng công việc của thuật toán khi đầu vào lớn lên. Nó không hỏi “máy chạy mất chính xác bao nhiêu mili-giây”, mà hỏi “khi dữ liệu tăng từ 100 lên 10.000 phần tử, lượng việc phải làm tăng theo kiểu nào”.

Khan Academy giải thích Big-O là một dạng giới hạn trên tiệm cận của thời gian chạy khi kích thước đầu vào đủ lớn. Nói thực dụng hơn: Big-O cho bạn biết tốc độ xấu đi của thuật toán khi dữ liệu phình ra. Nguồn: Khan Academy - Big-O notation.

MIT cũng dùng Big-O để mô tả “order of growth”, tức bậc tăng trưởng của hàm khi phân tích thuật toán. Nguồn: MIT - Big O notation PDF.

2. Hãy tưởng tượng bạn là người kiểm bài

Giả sử bạn có một danh sách học sinh. Bạn cần tìm một học sinh tên “An”.

Nếu danh sách chưa sắp xếp, bạn phải kiểm từng người từ đầu đến cuối:

function findStudent(students, name) {
  for (const student of students) {
    if (student.name === name) return student;
  }
  return null;
}

Nếu có 10 học sinh, trường hợp xấu nhất bạn kiểm 10 lần. Nếu có 1.000 học sinh, bạn có thể phải kiểm 1.000 lần. Nếu có 1.000.000 học sinh, bạn có thể phải kiểm 1.000.000 lần.

Đây là O(n), vì số việc tăng gần như cùng nhịp với số phần tử.

Cách nhớ: một vòng lặp đi qua toàn bộ dữ liệu thường là O(n).

3. Các mức Big-O thường gặp

O(1): lấy trực tiếp, không quan tâm dữ liệu nhiều hay ít

function getFirst(items) {
  return items[0];
}

Dù mảng có 10 hay 10 triệu phần tử, thao tác lấy phần tử đầu vẫn là một thao tác cố định về mặt ý tưởng thuật toán.

Cách nhớ: không có vòng lặp theo n, không tìm kiếm, không duyệt dữ liệu.

O(n): duyệt một lượt

function sum(numbers) {
  let total = 0;
  for (const number of numbers) {
    total += number;
  }
  return total;
}

Có bao nhiêu phần tử thì cộng bấy nhiêu lần. 100 phần tử thì khoảng 100 lượt, 1 triệu phần tử thì khoảng 1 triệu lượt.

O(n²): mỗi phần tử lại so với nhiều phần tử khác

function hasDuplicate(numbers) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] === numbers[j]) return true;
    }
  }
  return false;
}

Đây là ví dụ kinh điển của vòng lặp lồng nhau. Khi n tăng gấp 10 lần, lượng so sánh có thể tăng gần 100 lần.

Cách nhớ: hai vòng lặp phụ thuộc cùng một dữ liệu thường là O(n²).

O(log n): mỗi bước loại bỏ một phần lớn dữ liệu

Ví dụ phổ biến là tìm kiếm nhị phân trong mảng đã sắp xếp.

function binarySearch(sortedNumbers, target) {
  let left = 0;
  let right = sortedNumbers.length - 1;

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

    if (sortedNumbers[mid] === target) return mid;
    if (sortedNumbers[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

Mỗi lần kiểm tra, bạn bỏ được khoảng một nửa dữ liệu còn lại. Với 1.000.000 phần tử, số lần chia đôi chỉ khoảng 20 lần.

Khan Academy có phần riêng về binary search và running time, dùng để minh họa rất tốt cho kiểu tăng trưởng này. Nguồn: Khan Academy - Algorithms.

O(n log n): thường gặp trong các thuật toán sắp xếp tốt

Nhiều thuật toán sắp xếp hiệu quả có mức tăng trưởng O(n log n). Ý tưởng đơn giản: vừa phải xử lý toàn bộ n phần tử, vừa có yếu tố chia nhỏ hoặc trộn theo nhiều tầng.

Bạn không cần nhớ máy móc ngay từ đầu. Chỉ cần nhớ: nếu bài toán liên quan đến sắp xếp hiệu quả, O(n log n) là mức rất hay xuất hiện.

4. Cách đọc Big-O từ code: quy trình 4 bước

Bước 1: Xác định n là gì. n có thể là số user, số dòng dữ liệu, số item trong mảng, số node trong cây, số ký tự trong chuỗi.

Bước 2: Tìm vòng lặp hoặc thao tác lặp theo n. Một vòng chạy qua toàn bộ mảng thường là O(n).

Bước 3: Xem vòng lặp có lồng nhau không. Nếu mỗi phần tử lại duyệt qua toàn bộ danh sách, thường là O(n²).

Bước 4: Bỏ hằng số và phần nhỏ hơn. O(2n) viết thành O(n). O(n + 100) viết thành O(n). O(n² + n) viết thành O(n²), vì khi n lớn, n² áp đảo.

5. Ví dụ giảng từng bước: tối ưu tìm phần tử trùng

Bài toán: kiểm tra mảng có phần tử trùng không.

Cách 1: so sánh từng cặp.

function hasDuplicateSlow(numbers) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] === numbers[j]) return true;
    }
  }
  return false;
}

Phân tích: vòng ngoài chạy theo n. Với mỗi lượt vòng ngoài, vòng trong lại chạy qua nhiều phần tử còn lại. Tổng thể là O(n²).

Cách 2: dùng Set để ghi nhớ phần tử đã thấy.

function hasDuplicateFast(numbers) {
  const seen = new Set();

  for (const number of numbers) {
    if (seen.has(number)) return true;
    seen.add(number);
  }

  return false;
}

Phân tích: ta chỉ duyệt mảng một lần. Về mặt tư duy thuật toán, cách này thường được xem là O(n) trung bình, đổi lại cần thêm bộ nhớ O(n) để lưu Set.

Bài học: tối ưu thuật toán thường là đổi thời gian lấy bộ nhớ.

6. Time complexity và space complexity

Time complexity hỏi: chương trình cần bao nhiêu bước khi dữ liệu tăng?

Space complexity hỏi: chương trình cần thêm bao nhiêu bộ nhớ khi dữ liệu tăng?

Ví dụ hasDuplicateSlow dùng ít bộ nhớ phụ, nhưng chạy chậm hơn: thời gian O(n²), bộ nhớ phụ O(1).

Ví dụ hasDuplicateFast chạy nhanh hơn, nhưng dùng thêm bộ nhớ: thời gian O(n), bộ nhớ phụ O(n).

Trong thực tế, không phải lúc nào O(n) cũng “tốt hơn tuyệt đối”. Nếu dữ liệu nhỏ, cách đơn giản đôi khi đủ dùng. Nếu dữ liệu lớn, Big-O bắt đầu rất quan trọng.

Princeton lưu ý rằng Big-O không nên bị hiểu sai như công cụ dự đoán hiệu năng chính xác; nó mô tả bậc tăng trưởng, còn tốc độ thực tế vẫn phụ thuộc phần cứng, ngôn ngữ, bộ nhớ đệm, runtime và cách triển khai. Nguồn: Princeton - Analysis of Algorithms.

7. Bảng nhớ nhanh

8. Những lỗi hiểu sai Big-O

Sai lầm 1: “Có hai vòng lặp là O(n²)”. Không luôn đúng. Nếu hai vòng lặp chạy nối tiếp, không lồng nhau, có thể chỉ là O(n + n), tức O(n).

function twoSeparateLoops(items) {
  for (const item of items) console.log(item);
  for (const item of items) console.log(item);
}

Đoạn này là O(n), không phải O(n²).

Sai lầm 2: “Big-O cho biết thời gian chạy chính xác”. Không đúng. Big-O nói về tốc độ tăng khi dữ liệu lớn, không phải số mili-giây cụ thể.

Sai lầm 3: “O(n) lúc nào cũng nhanh hơn O(n log n)”. Khi dữ liệu nhỏ hoặc hằng số ẩn lớn, kết quả thực tế có thể khác. Nhưng khi n rất lớn, bậc tăng trưởng thường thắng.

Sai lầm 4: “Chỉ cần tối ưu Big-O là xong”. Không đủ. Code còn cần đúng, dễ đọc, dễ bảo trì và phù hợp với dữ liệu thật.

9. Bài tập kiểm tra

Bài 1

Đoạn code sau là Big-O gì?

function printAll(items) {
  for (const item of items) {
    console.log(item);
  }
}

Bài 2

Đoạn code sau là Big-O gì?

function printPairs(items) {
  for (const a of items) {
    for (const b of items) {
      console.log(a, b);
    }
  }
}

Bài 3

Đoạn code sau là Big-O gì?

function printFirstThenAll(items) {
  console.log(items[0]);

  for (const item of items) {
    console.log(item);
  }
}

Bài 4

Bạn có 1 triệu username và cần kiểm tra một username có tồn tại không. Bạn sẽ thích cấu trúc nào hơn: mảng phải duyệt từng phần tử, hay cấu trúc tra cứu nhanh như Set/Map? Vì sao?

10. Đáp án

Bài 1: O(n). Có một vòng lặp đi qua toàn bộ dữ liệu.

Bài 2: O(n²). Với mỗi phần tử a, code lại duyệt qua mọi phần tử b.

Bài 3: O(n). Thao tác console.log(items[0]) là O(1), vòng lặp là O(n), tổng là O(n + 1), rút gọn thành O(n).

Bài 4: Nên ưu tiên Set/Map nếu cần kiểm tra tồn tại nhiều lần trên dữ liệu lớn. Lý do là cách duyệt mảng tuyến tính có thể phải kiểm tra rất nhiều phần tử, còn cấu trúc tra cứu được thiết kế để tìm nhanh hơn trong thực tế. Cần nhớ rằng đổi lại bạn thường phải dùng thêm bộ nhớ.

11. Checklist khi phân tích code thực tế

• n là gì?
• Có vòng lặp theo n không?
• Vòng lặp có lồng nhau không?
• Có thao tác chia đôi dữ liệu không?
• Có tạo mảng/object/set/map mới theo kích thước đầu vào không?
• Đoạn code ưu tiên tiết kiệm thời gian hay tiết kiệm bộ nhớ?
• Dữ liệu thật có đủ lớn để cần tối ưu không?

12. Tóm tắt bài học

Big-O là công cụ để đọc “tốc độ phình ra” của thuật toán. Người mới học không cần biến nó thành toán học nặng ngay từ đầu. Hãy bắt đầu bằng cách nhìn vòng lặp, dữ liệu đầu vào và số lần chương trình phải làm việc.

Nếu code duyệt một lượt, thường nghĩ đến O(n). Nếu code có hai vòng lặp lồng nhau trên cùng dữ liệu, hãy nghi ngờ O(n²). Nếu mỗi bước loại bỏ một nửa dữ liệu, hãy nghĩ đến O(log n). Nếu tối ưu từ O(n²) xuống O(n), thường bạn đang đổi thêm bộ nhớ để giảm thời gian.

Nguồn tham khảo

• Khan Academy - Big-O notation
• Khan Academy - Algorithms
• MIT - Big O notation PDF
• Princeton - Analysis of Algorithms
• Python Wiki - TimeComplexity