Giới thiệu trực quan về ký pháp Big O

(samwho.dev)

2 điểm bởi GN⁺ 2025-08-26 | Chưa có bình luận nào. | Chia sẻ qua WhatsApp

Ký pháp Big O biểu diễn mẫu tăng trưởng theo sự thay đổi của kích thước đầu vào của hiệu năng hàm
Bài viết giải thích các dạng Big O tiêu biểu như hằng số, logarit, tuyến tính, bậc hai kèm ví dụ
Tùy vào cấu trúc dữ liệu và thuật toán, độ phức tạp thời gian sẽ khác nhau, thể hiện rõ trong các tác vụ như sắp xếp mảng, tìm kiếm
Để cải thiện hiệu năng mã thực tế, cốt lõi là chọn cấu trúc dữ liệu phù hợp và loại bỏ các phép tính không cần thiết trong vòng lặp
Big O luôn biểu diễn theo cách đơn giản hóa nhất mối quan hệ giữa đầu vào và thời gian chạy, và khi tối ưu hiệu năng thì việc đo đạc mã trực tiếp là rất quan trọng

Tổng quan về ký pháp Big O

Ký pháp Big O là cách mô tả mẫu tăng trưởng của thời gian chạy theo kích thước đầu vào (n) thay vì đo thời gian trực tiếp
Nó phân loại thời gian chạy của hàm theo đầu vào, chủ yếu phân tích các dạng hằng số (O(1)), logarit (O(log n)), tuyến tính (O(n)), bậc hai (O(n²))
Bài viết này giải thích khái niệm của từng dạng bằng ví dụ trực quan và ví dụ mã thực tế để cả người mới bắt đầu cũng có thể hiểu được

Lặp (Iterating) và thuật toán tuyến tính

Hàm sum(n) là ví dụ về cấu trúc lặp để cộng từ 1 đến n; khi giá trị đầu vào n tăng lên thì thời gian thực thi cũng tăng tỉ lệ thuận
Thực tế, sum(1e9) mất khoảng 1 giây, sum(2e9) mất khoảng 2 giây, nên thời gian đồng hồ thực (wall-clock time) tăng theo mẫu O(n)
Độ phức tạp thời gian là mối quan hệ giữa đầu vào của hàm và thời gian chạy, và được biểu diễn bằng ký pháp Big O (O(n) — tỉ lệ với n)
Nếu dùng công thức toán học sum(n) = (n*(n+1))/2 thay vì lặp, thời gian thực thi sẽ cố định (hằng số) bất kể giá trị đầu vào n
Những hàm như vậy được gọi là có độ phức tạp thời gian hằng số O(1), đặc trưng là không có tăng trưởng thời gian chạy theo sự thay đổi của đầu vào

Cú pháp của ký pháp Big O

Chữ O trong Big O bắt nguồn từ “Order” và chỉ biểu thị chính dạng tăng trưởng
Nó không biểu thị giá trị tuyệt đối của thời gian chạy, mà chỉ ghi ngắn gọn 'mẫu' tăng trưởng so với đầu vào
Ví dụ, dù là hàm O(n), người ta không viết phức tạp như 'O(2n)' hay 'O(n+1)', mà chỉ chọn hạng đơn giản nhất

Rút ngắn thời gian bằng cách cải tiến thuật toán

Như ví dụ công thức sum(n), có thể chuyển độ phức tạp thời gian từ O(n) sang O(1) thông qua cải tiến thuật toán
Tuy nhiên, có độ phức tạp hằng số không đồng nghĩa lúc nào cũng nhanh hơn, vì tổng thời gian chạy vẫn phụ thuộc vào loại phép toán thực hiện
Một thuật toán O(n) có thể nhanh hơn O(1) trong một số đầu vào cụ thể, nhưng khi kích thước đầu vào tăng lên thì cách O(1) cuối cùng sẽ chiếm ưu thế

Sắp xếp (Sorting) và thuật toán bậc hai (Quadratic): ví dụ Bubble Sort

Bubble Sort là ví dụ cơ bản về việc sắp xếp mảng bằng cách lặp lại thao tác đổi chỗ các số kề nhau
Nếu mảng đã được sắp xếp thì chỉ cần 1 lượt lặp (O(n)); nếu ở thứ tự ngược thì cần duyệt lặp lại n lần → trường hợp xấu nhất có tổng số phép toán là n²
Thuật toán O(n²) có thời gian thực thi tăng rất mạnh theo dạng bậc hai khi đầu vào lớn dần
Trong thực tế, Big O luôn dựa trên trường hợp xấu nhất (worst-case) làm chuẩn (dù đôi khi cũng ghi thêm trung bình/tốt nhất)
Số lần lặp có thể giảm tùy trạng thái ban đầu của mảng, nhưng do xét trường hợp xấu nhất nên vẫn luôn được phân loại là độ phức tạp thời gian bậc hai

Tìm kiếm (Searching) và thuật toán logarit: ví dụ Binary Search

Binary Search ước lượng giá trị ở giữa của một phạm vi đã sắp xếp, rồi loại bỏ một nửa vùng ứng viên ở mỗi bước
Ví dụ, để đoán một số cụ thể trong khoảng 1~100 chỉ cần tối đa 7 lần; với 1~1 tỷ cũng có thể làm được trong dưới 31 lần thử
Vì danh sách ứng viên giảm một nửa sau mỗi bước, thời gian chạy là O(log n) (độ phức tạp thời gian logarit)
Thuật toán logarit tăng rất chậm khi n lớn lên, nên hiệu quả vượt trội so với tuyến tính hoặc bậc hai
Khi so sánh trên đồ thị, sự khác biệt tăng trưởng giữa log n, n, n² hiện ra rất rõ ràng

Ứng dụng thực tế: mẹo cải thiện độ phức tạp thời gian

Tìm mục trong danh sách

Về cơ bản, hàm tìm một giá trị trong mảng thuộc loại O(n)
Nếu cần tìm kiếm thường xuyên, dùng cấu trúc dữ liệu như Set có thể cải thiện xuống O(1)
Tuy nhiên, quá trình chuyển đổi bằng new Set(array) tự nó đã là O(n), nên chỉ phù hợp khi tra cứu lặp lại nhiều lần (cần tính chi phí chuyển đổi)
Ví dụ: items.has("banana") cung cấp độ phức tạp thời gian hằng số

Viết vòng lặp tận dụng chỉ mục

Đoạn mã dùng .indexOf bên trong vòng lặp như dưới đây là nguyên nhân phổ biến gây ra vấn đề hiệu năng

function buildList(items) {
  const output = [];
  for (const item of items) {
    const index = items.indexOf(item);
    output.push(`Item ${index + 1}: ${item}`);
  }
  return output.join("\n");
}

Vì .indexOf là phép toán O(n) khi nằm trong vòng lặp, nên toàn bộ trở thành mẫu O(n^2)

Dùng vòng lặp theo chỉ mục hoặc forEach((item, index) => ...) sẽ cải thiện thành O(n)

function buildList(items) {
  const output = [];
  for (let i = 0; i < items.length; i++) {
    output.push(`Item ${i + 1}: ${items[i]}`);
  }
  return output.join("\n");
}

Tận dụng memoization

Với các cấu trúc bị tính lặp lại như giai thừa, có thể cải thiện hiệu năng bằng cách cache kết quả (dùng Map)
Việc tra cứu trong Map là O(1), giúp giảm thiểu tính toán lại không cần thiết

Tuy nhiên, cache chủ yếu cải thiện thời gian trung bình; dù độ phức tạp thời gian tệ nhất có thể không đổi, hiệu năng thực tế vẫn được cải thiện đáng kể

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;
}

Đánh giá hiệu năng và kết luận

Khi cải thiện hiệu năng mã, cần xác nhận mức cải thiện thực tế bằng kiểm thử chạy trực tiếp cùng với độ phức tạp thời gian về mặt lý thuyết
Big O biểu diễn theo cách đơn giản hóa nhất mối quan hệ và mẫu tăng trưởng giữa đầu vào và thời gian chạy
Có thể tối đa hóa hiệu quả mã bằng cách chọn thuật toán tốt và tối ưu cấu trúc dữ liệu

Tóm tắt

Ký pháp Big O biểu diễn mối quan hệ giữa giá trị đầu vào của hàm và thời gian chạy
Các mức hiệu năng chính: O(1) (hằng số), O(log n) (logarit), O(n) (tuyến tính), O(n^2) (bậc hai)
Để viết mã hiệu quả, việc tối ưu thuật toán và vòng lặp phù hợp là rất quan trọng
Hiệu năng thực tế cần được đo trực tiếp để xác minh hiệu quả cải thiện
Có thể dùng đồ thị so sánh mẫu tăng trưởng để nắm bắt nhanh đặc trưng của độ phức tạp thời gian