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

(samwho.dev)

2 điểm bởi GN⁺ 2025-08-26 | 1 bình luận | 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

1 bình luận

GN⁺ 2025-08-26

Ý kiến trên Hacker News

Bài viết này và cả các bình luận trên HN cũng đang tiếp tục truyền thống vừa giải thích Big O Notation, vừa tranh luận về cách áp dụng thực tế và các chi tiết kỹ thuật. Có thể tham khảo bài giải thích này và bài viết về thái độ của chuyên gia
- Xem lại bình luận ở bài trước thì có một người dùng tên Pyon tỏ ra cay nghiệt và cứng nhắc. Nhưng phản hồi của Ned cũng không hẳn xuất sắc. Ông ấy không giải thích chính xác các chi tiết kỹ thuật, mà chỉ lặp đi lặp lại cách nói vòng vo kiểu “một số chi tiết cụ thể”. Cũng khá đáng tiếc vì không làm rõ vì sao lời chỉ trích đó chỉ là bắt bẻ vụn vặt, và vì sao lại bác bỏ luôn cả nội dung. Dù vậy, Ned vẫn thể hiện được định hướng đúng về giao tiếp và sự đồng cảm trên mạng. Tuy nhiên, nếu là một người làm giáo dục thì tôi vẫn muốn ông ấy ít nhất chỉ ra vì sao luận điểm kỹ thuật đó là quá tiểu tiết hay chỉ là bắt bẻ. Bản thân Ned chỉ nói rằng ông ấy “đã không biết điều đó suốt hàng chục năm”, nên cảm giác như vậy vẫn chưa đủ. Và khi tôi xem lại chuỗi bình luận gốc thì thực ra Ned đã tranh luận khá ngoại giao và nghiêm túc. Vì thế tôi thắc mắc tại sao phần phân tích đó lại bị lược mất trong bài blog. Cá nhân tôi cũng không rõ chính xác các chi tiết kỹ thuật đó là gì, nhưng vẫn mong có ai đó tóm tắt ngắn gọn một lần
- Tôi thuộc kiểu chuyên gia hay phê bình. Mỗi khi thấy các blog cố dạy những chủ đề phức tạp, tôi thường thất vọng vì đa phần là người không chuyên giải thích nên đánh rơi tính chính xác. Kết quả là 1) nội dung sai bị copy-paste khắp Internet, và 2) người đọc chỉ dừng ở mức hiểu kiểu blog rồi không học thêm nữa, từ đó càng củng cố sự thiếu hiểu biết. Ngoài ra, tôi cũng không thích bố cục trang. Theo trải nghiệm của tôi với ADHD và trí nhớ kém, nội dung cần được chia nhịp bằng định dạng phù hợp như tiêu đề phụ/in đậm/màu phân tách/bullet thì tôi mới theo được, còn bài này tạo cảm giác như một bức tường chữ. Càng mất nhiều thời gian để nắm ý chính thì tôi càng dễ mất tập trung. Phần giải thích về Big O trên Simple Wikipedia thẳng thắn hơn nhiều. Còn trang Wikipedia chính thức thì toán học xuất hiện đột ngột, và khi tự xem sẽ thấy Big O thực ra là một chủ đề phức tạp hơn nhiều so với tưởng tượng, khiến tôi đi đến kết luận rằng “đơn giản hóa quá mức có khi lại không tốt”
- Link thứ hai không nói về Big-O, và cũng chẳng có lý do gì để noi theo kiểu thái độ đó
- Ned đã gửi email cho tôi vài ngày trước, và tôi cũng vui khi có thể đóng góp vào cuộc thảo luận này
- Điều thực sự nên rút ra từ những chuyện như thế này không phải là “nếu có lời giải thích sai hoặc dễ gây hiểu nhầm thì đừng sửa”, mà là trên mạng có những “chuyên gia” chỉ muốn thắng tranh luận. Nhìn thái độ của Pyon thì khá hung hăng và giống Internet troll. Tuyệt đối không nên đi đến kết luận rằng “vậy thì chi tiết kỹ thuật không quan trọng và không chính xác cũng không sao”
O(1) trên thực tế thường dùng hàm băm, thứ không hẳn đơn giản nhưng vẫn tốn một lượng tính toán cố định. Nếu dữ liệu rất nhỏ thì ngay cả thuật toán tệ nhất như O(n^2) cũng có thể nhanh hơn về thời gian thực tế
- Đúng, nhưng cũng không nên nhấn quá mạnh điều đó. Trong thực tế, chỉ để người ta hiểu rằng n^2 là kiểu khiến máy tính khựng lại đã đủ khó rồi. Hơn nữa trong một số trường hợp còn có thể dùng hàm băm hoàn hảo như mod
Tôi có cảm giác tầm quan trọng của Big-O trong thời hiện đại không còn như trước. Phần cứng ngày nay có đa luồng, pipeline, NUMA, caching phức tạp, nên có những phép toán xong trong chưa tới một chu kỳ, trong khi có những phép toán khác lại mất hàng trăm đến hàng nghìn chu kỳ. Nếu cứ cố mô tả thuật toán chỉ bằng số lần chạy của innermost loop thì ngược lại sẽ làm méo mó thực tế. Và khi nói về Big-O thì cũng phải nhắc đến các ký hiệu khác như Big-Omega. (Nhân tiện, tôi cũng rất thích bộ hoạt hình lấy Big-O làm chủ đề)
- Lý thuyết Big-O ra đời chính là để định nghĩa lượng tính toán theo cách không phụ thuộc vào những yếu tố gắn với thiết bị như thế. Theo nghĩa đó, đây là một công cụ không lỗi thời. (Một người thuyết trình tử tế thường cũng sẽ luôn nhắc rằng “các hằng số như C có thể rất quan trọng khi N còn nhỏ”)
Điều thật sự thú vị là trong điện toán lượng tử, có những phép tính tăng theo O(n^7) theo số lượng nguyên tử, nhưng các nhà khoa học vẫn không ngại chạy chúng. Bởi vì N đủ nhỏ, máy tính và bộ nhớ vẫn tiếp tục nhanh hơn, và giá trị của kết quả thì cực kỳ lớn. (Tôi không phải chuyên gia khoa học máy tính, nên nếu dùng ký hiệu O() chưa đúng thì xin bỏ qua)
- Chỉ cần nói là “tăng tỷ lệ với n^7” là được. Nếu nói O(n^7) thì đa số vẫn hiểu, nhưng về mặt toán học thì O chỉ biểu thị “cận trên”, nên không thật sự chính xác theo nghĩa nghiêm ngặt. Muốn nói thật chính xác thì nên viết kiểu như Ω(n^7)
Tôi rất thích phần trực quan hóa. Ngay cả với người từng học thuật toán như tôi thì việc nhìn theo cách trực quan vẫn cực kỳ hữu ích
Có lẽ vì tôi học điện kỹ nên Big O Notation lúc nào cũng bị dạy như một khái niệm bị lướt qua cho xong. Nó luôn được xem như thứ ai cũng đương nhiên biết, nên tôi không nhớ từng thấy ai giải thích nó thật sự tử tế. Tôi tò mò không biết khái niệm này thường được giới thiệu lần đầu ở mức độ nào trong chương trình toán hoặc khoa học máy tính
- Tôi học Big-O bài bản nhất trong giờ Discrete Math của chương trình khoa học máy tính
- Ở trường tôi, môn Algorithm Analysis (bắt buộc) dạy Big-O và nhiều phương pháp chứng minh khác nhau. Nhưng đó gần như là môn năm 3 hoặc năm 4, và trên thực tế vẫn có giả định ngầm rằng sinh viên đến khoảng năm 1 là đã hấp thụ được phần nào khái niệm này rồi, có lẽ do tự nhiên học được từ xung quanh
- Về mặt toán học, việc hàm f(x) là O(g(x)) có nghĩa là f(x)/g(x) thỏa mãn điều kiện “với mọi x, f(x)/g(x) < C” đối với một hằng số C nào đó. Trong khoa học máy tính, f(x) thường biểu diễn độ phức tạp như số phép tính của một thuật toán cụ thể
- Cách thiết kế Big-O Notation cho phép nhiều cách diễn giải. Ví dụ, nếu định nghĩa một thuật toán bằng số bước chạy trên Turing Machine thì sẽ không thể có thuật toán thời gian log, và O(log n) sẽ được xem là O(1)
- Tôi học nó trong môn bắt buộc năm nhất ngành khoa học máy tính. Thực ra không có gì ghê gớm, chỉ là cách mô tả lượng phép tính tăng như thế nào khi dữ liệu đầu vào nhiều lên. Nhìn qua thì có vẻ khó, nhưng thực chất rất đơn giản và rõ ràng
Phần trực quan động giúp tôi hiểu hơn rất nhiều. Mong sẽ có thêm nhiều bài học/tài liệu như thế này
- Nghe vậy thật đáng quý và rất vui
Mỗi lần có thread về Big-O Notation xuất hiện là tôi lại hy vọng có ai đó giải thích giúp khái niệm này liên hệ thế nào với anime The Big O. Đến giờ tôi vẫn không thật sự hiểu anime đó nói về cái gì
- (Nốc liền 4 lon bia)Được rồi nghe này. Anime đó giống như lần lượt trộn Pacific Rim, Dark City và The Matrix vào với nhau
Cá nhân tôi thấy cách hiệu quả nhất để hiểu Big O Notation là liên hệ nó với những ví dụ đời thường
Tôi nghĩ đây là một tài liệu rất đẹp. Tôi đã gửi tín hiệu rồi, hy vọng đã truyền tới nơi, cảm giác như vô tình được thêm một muỗng dopamine vậy
- Đã nhận được rồi. Cảm ơn