Bảng Big-O hữu ích cho đến khi nó thay thế việc suy luận. Bảng cho biết truy cập mảng là hằng số, sắp xếp là O(nlog⁡n)O(n \log n) và tra cứu hash table là hằng số “trung bình”. Nó không cho biết thao tác đang được tính, phân phối đầu vào, dữ liệu có nằm trong cache hay thời gian đọc từ cơ sở dữ liệu có lớn hơn phần thuật toán hay không.

Phân tích tiệm cận là ngôn ngữ mô tả tài nguyên thay đổi thế nào khi đầu vào tăng, không phải đồng hồ bấm giờ. Dùng đúng, nó loại bỏ thiết kế không thể mở rộng và so sánh thuật toán độc lập với một máy cụ thể. Dùng máy móc, nó che mất giả định và tạo ra câu trả lời không liên quan đến bài toán thật.

Vì vậy, mục tiêu không phải học thuộc thêm một bảng tra cứu. Ta cần một quy trình lặp lại được: định nghĩa đầu vào, chọn thao tác và trường hợp cần xét, suy ra cận thời gian lẫn không gian, xem xét chi phí ở cấp máy, rồi đo các implementation đại diện.

Cận mô tả tốc độ tăng, không mô tả thời gian chạy

Gọi f(n)f(n) là chi phí của thuật toán và g(n)g(n) là một hàm tham chiếu đơn giản hơn. Big-O là cận trên tiệm cận: từ một kích thước đầu vào đủ lớn, một bội số hằng của g(n)g(n) luôn nằm trên f(n)f(n).

f(n)=O(g(n))  ⟺  ∃c>0,∃n0,∀n≥n0:0≤f(n)≤cg(n)f(n) = O(g(n)) \iff \exists c > 0, \exists n_0, \forall n \ge n_0: 0 \le f(n) \le c g(n)

Cận dưới và cận chặt tương ứng là:

f(n)=Ω(g(n))  ⟺  ∃c>0,∃n0,∀n≥n0:0≤cg(n)≤f(n)f(n) = \Omega(g(n)) \iff \exists c > 0, \exists n_0, \forall n \ge n_0: 0 \le c g(n) \le f(n)
f(n)=Θ(g(n))  ⟺  f(n)=O(g(n))∧f(n)=Ω(g(n))f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \land f(n) = \Omega(g(n))

Các định nghĩa này chỉ ra hai nhầm lẫn phổ biến. Thứ nhất, Big-O không đồng nghĩa với “trường hợp xấu nhất.” Một cận trên có thể mô tả chi phí tốt nhất, trung bình hoặc xấu nhất; trường hợp đang xét và loại cận là hai thông tin độc lập. Thứ hai, một cận trên chưa chắc là mô tả giàu thông tin nhất. Quét tuyến tính cũng thuộc O(n2)O(n^2) vì một hàm bậc hai cuối cùng vẫn chặn được nó, nhưng Θ(n)\Theta(n) mới diễn đạt chặt tốc độ tăng thực sự.

Phát biểu Điều được bảo đảm Câu hỏi phù hợp
O(g(n))O(g(n)) Tốc độ tăng không vượt quá một trần tiệm cận Khi đầu vào tăng, chi phí có vượt năng lực hệ thống không?
Ω(g(n))\Omega(g(n)) Tốc độ tăng không thấp hơn một sàn tiệm cận Có lượng công việc nền tảng nào không thể tránh không?
Θ(g(n))\Theta(g(n)) Cận trên và cận dưới trùng nhau Lớp tăng trưởng thực sự của thuật toán là gì?
Chi phí chính xác hoặc thực nghiệm Có cả hằng số và hành vi quan sát được Implementation nào thắng trong miền vận hành thật?

Bỏ hằng số không có nghĩa hằng số không quan trọng: 3n+203n+20 và 1000n+51000n+5 đều tuyến tính, nhưng implementation thứ hai vẫn có thể chậm hơn trong mọi kích thước production. Phân tích tiệm cận thu hẹp tập ứng viên; đo đạc chọn giữa các ứng viên còn lại.

Warning

Đừng chỉ báo cáo “đoạn này là O(n)O(n).” Hãy nêu tài nguyên, biến đầu vào, thao tác và trường hợp: “Một lần tra cứu quét nhiều nhất nn record, nên thời gian CPU trong trường hợp xấu nhất là Θ(n)\Theta(n) và bộ nhớ phụ trợ là Θ(1)\Theta(1).”

Chọn mô hình đầu vào và trường hợp cần phân tích

Ký hiệu nn không có ý nghĩa cho đến khi được định nghĩa. Với thuật toán xử lý chuỗi, nn có thể là số Unicode code point, UTF-16 code unit hoặc byte. Với đồ thị, mô hình hữu ích thường có hai biến: VV đỉnh và EE cạnh. Breadth-first search dùng adjacency list có độ phức tạp Θ(V+E)\Theta(V+E), không chỉ đơn giản là “tuyến tính.” Với phép nhân ma trận, các chiều quan trọng hơn số lượng ma trận. Với thuật toán số nguyên, độ phức tạp có thể phụ thuộc số bit, nên phép toán trên số nguyên không giới hạn không mặc nhiên là hằng số.

Cách biểu diễn dữ liệu thuộc mô hình. Binary search thực hiện Θ(log⁡n)\Theta(\log n) phép so sánh trên mảng đã sắp xếp có random access. Trên linked list, tìm node giữa mất thời gian tuyến tính nếu không có thêm cấu trúc. Hash table cho tra cứu kỳ vọng hằng số khi giả định về hàm băm, load factor và resize đúng; collision đối kháng có thể biến tra cứu thành tuyến tính.

Các trường hợp trả lời những câu hỏi khác nhau:

  • Trường hợp xấu nhất đưa ra trần cho mọi đầu vào hợp lệ có kích thước nn. Nó quan trọng với ngân sách latency, biên bảo mật và hệ thống thời gian thực.
  • Trường hợp trung bình là kỳ vọng trên một phân phối xác suất được nêu rõ. “Thông thường” không phải là một phân phối. Key ngẫu nhiên đều có thể là mô hình tệ cho timestamp, ID đã sắp xếp hoặc request do kẻ tấn công kiểm soát.
  • Chi phí khấu hao trải chi phí của cả chuỗi thao tác mà không giả định đầu vào ngẫu nhiên. Nó chứng minh rằng các thao tác đắt thỉnh thoảng xuất hiện đã được nhiều thao tác rẻ chi trả.
flowchart TD A[Định nghĩa thao tác và đầu vào tăng trưởng] --> B{Đầu vào có thể tăng đáng kể?} B -- Không --> C[Đo các kích thước cố định thực tế] B -- Có --> D[Suy ra cận thời gian và không gian] D --> E{Có thao tác hiếm nhưng đắt?} E -- Có --> F[Thêm phân tích khấu hao] E -- Không --> G[Nêu trường hợp xấu nhất và trung bình] F --> H[Benchmark các ứng viên đại diện] G --> H C --> H H --> I[Kiểm tra cache allocation và I O] I --> J[Chọn theo ràng buộc sản phẩm]

Trình tự này giữ phân tích gắn với quyết định. Một tập cố định gồm mười hai HTTP route không cần cấu trúc dữ liệu tiệm cận cầu kỳ. Một queue có thể chứa mười triệu job thì có. Tốc độ tăng trở nên quan trọng khi miền vận hành có thể vượt qua một ngưỡng đáng kể.

Đọc code, rồi đọc cách máy thực thi

Xét bài toán phát hiện phần tử trùng. Phiên bản hai vòng lặp dùng bộ nhớ phụ trợ hằng số và thực hiện tối đa xấp xỉ n(n−1)/2n(n-1)/2 phép so sánh bằng nhau. Phiên bản dùng set đi qua dữ liệu một lần, tốn thêm bộ nhớ tuyến tính và dựa trên thao tác Set có thời gian kỳ vọng hằng số.

ts
export function hasDuplicatePairwise(values: readonly number[]): boolean {
  for (let left = 0; left < values.length; left += 1) {
    for (let right = left + 1; right < values.length; right += 1) {
      if (values[left] === values[right]) {
        return true;
      }
    }
  }
  return false;
}

export function hasDuplicateWithSet(values: readonly number[]): boolean {
  const seen = new Set<number>();

  for (const value of values) {
    if (seen.has(value)) {
      return true;
    }
    seen.add(value);
  }

  return false;
}

Với đầu vào không có phần tử trùng, hàm pairwise có thời gian Θ(n2)\Theta(n^2) và bộ nhớ phụ trợ Θ(1)\Theta(1). Hàm dùng set có thời gian kỳ vọng Θ(n)\Theta(n) và bộ nhớ phụ trợ Θ(n)\Theta(n). Nếu phần tử ở hai vị trí đầu đã trùng nhau, cả hai trả về sau lượng công việc hằng số. Trường hợp tốt nhất đó không thay đổi hành vi xấu nhất.

Phiên bản tuyến tính thường dễ mở rộng hơn, nhưng Set phải cấp phát, băm giá trị, đi theo pointer và có thể kích hoạt garbage collection. Vòng quét lồng nhau trên mảng nhỏ có branch đơn giản và locality tốt, nên có thể thắng với tám giá trị nhưng gần như chắc chắn thua với tám triệu giá trị.

Cache locality giải thích nhiều bất ngờ. Truy cập mảng tuần tự giúp phần cứng prefetch cache line, trong khi tree và linked list nhiều pointer có thể phải chờ bộ nhớ dù ít phép so sánh hơn. Branch prediction, vectorization, allocation và object layout đều làm thay đổi hằng số.

I/O còn thay đổi thang đo mạnh hơn. Một lượt quét O(n)O(n) trong bộ nhớ có thể hoàn tất trước một network round trip. Ngược lại, một truy vấn cơ sở dữ liệu được gọi là O(1)O(1) vẫn có thể đọc đĩa, chờ lock, serialize và truyền qua mạng. Hãy đếm thao tác logic, đồng thời đếm các đường biên: số query, số byte đọc, lời gọi từ xa và điểm đồng bộ. Gom 1.000 key vào một request vẫn tuyến tính theo số key, nhưng có thể nhanh hơn rất nhiều so với 1.000 request từ xa mà mỗi request được coi là hằng số.

Tip

Hãy dùng phân tích tiệm cận tại từng tầng tốn kém. Mô tả công việc CPU theo record, công việc storage theo page hoặc byte, và công việc phân tán theo request cùng round trip. Một nhãn Big-O hiếm khi mô tả đủ cả service.

Khấu hao và không gian là các ràng buộc hạng nhất

Dynamic array cho thấy vì sao một thao tác riêng lẻ và cả chuỗi thao tác có thể mang chi phí khác nhau. Phần lớn lần append chỉ ghi một phần tử. Khi hết capacity, append phải cấp phát buffer lớn hơn và sao chép các phần tử hiện có, khiến riêng thao tác ấy tốn Θ(n)\Theta(n). Nếu capacity tăng gấp đôi mỗi lần, số lần sao chép trong mm thao tác append tạo thành cấp số nhân:

1+2+4+⋯+2k<2m1 + 2 + 4 + \cdots + 2^k < 2m

Tổng công việc là tuyến tính, vì thế chi phí append khấu hao là hằng số:

∑i=1mcim=O(1)\frac{\sum_{i=1}^{m} c_i}{m} = O(1)

Đây không phải trường hợp trung bình: ta không cần phân phối ngẫu nhiên và một lần append vẫn có thể chậm. Phân tích tổng hợp chia tổng chi phí cho chuỗi; phương pháp accounting để thao tác rẻ dành credit cho lần resize; phương pháp potential theo dõi công việc bằng hàm thế năng. Mọi phương pháp đều phải trả đủ chi phí.

Bảo đảm khấu hao rất tốt cho throughput nhưng có thể chưa đủ với tail latency. Một UI frame, audio callback hoặc vòng điều khiển thời gian thực có thể trễ deadline đúng vào lần append phải resize. Cấp phát trước, resize tăng dần hoặc một cấu trúc dữ liệu có cận xấu nhất chặt hơn có thể xứng đáng với độ phức tạp bổ sung.

Phân tích không gian cần chính xác như phân tích thời gian. Hãy phân biệt không gian đầu vào và không gian phụ trợ. Hàm phát hiện trùng bằng set nhận nn giá trị và lưu thêm tối đa nn entry, nên bộ nhớ phụ trợ là Θ(n)\Theta(n). Một phép duyệt depth-first đệ quy có thể không cấp phát collection tường minh nhưng vẫn dùng Θ(h)\Theta(h) stack frame, với hh là chiều cao cây. Cây cân bằng có h=Θ(log⁡n)h=\Theta(\log n); cây suy biến có h=Θ(n)h=\Theta(n).

Cần xem peak live memory thay vì chỉ tổng cấp phát. Streaming có thể xử lý một terabyte với bộ nhớ bị chặn dù I/O tuyến tính. Pipeline giữ nhiều bản sao có thể vượt memory limit trước khi CPU thành nút thắt; trong managed runtime, allocation còn tăng thời gian garbage collection.

Benchmark mà không đo một ảo ảnh

Benchmark cần kiểm tra một giả thuyết về miền vận hành, không phải tạo ra người thắng theo ý muốn. Với JavaScript và TypeScript, các bẫy thường gặp gồm JIT warmup, dead-code elimination, nhiễu bộ đếm thời gian, garbage collection, mutation đầu vào, I/O vô tình lọt vào và dữ liệu test thiên vị một branch. Chạy hàm một lần bằng Date.now() thường đo startup cùng nhiễu scheduling nhiều hơn đo thuật toán.

Harness Node.js dưới đây dùng đầu vào tất định, warm up từng ứng viên, tiêu thụ kết quả qua checksum, chạy nhiều sample và báo median. Nó cố ý nhỏ gọn, nhưng là điểm xuất phát có cơ sở.

ts
import { performance } from 'node:perf_hooks';

type Candidate = (values: readonly number[]) => boolean;

function makeUniqueValues(size: number): number[] {
  return Array.from({ length: size }, (_, index) => index * 2 + 1);
}

function median(samples: readonly number[]): number {
  const sorted = [...samples].sort((left, right) => left - right);
  const middle = Math.floor(sorted.length / 2);
  const value = sorted[middle];
  if (value === undefined) {
    throw new Error('At least one sample is required');
  }
  return value;
}

function measure(
  candidate: Candidate,
  values: readonly number[],
  iterations: number,
): { milliseconds: number; checksum: number } {
  let checksum = 0;

  for (let warmup = 0; warmup < 20; warmup += 1) {
    checksum ^= Number(candidate(values));
  }

  const samples: number[] = [];
  for (let sample = 0; sample < 15; sample += 1) {
    const startedAt = performance.now();
    for (let iteration = 0; iteration < iterations; iteration += 1) {
      checksum ^= Number(candidate(values));
    }
    samples.push(performance.now() - startedAt);
  }

  return { milliseconds: median(samples), checksum };
}

for (const size of [8, 64, 512, 4096]) {
  const values = makeUniqueValues(size);
  const iterations = Math.max(1, Math.floor(20_000 / size));

  console.log({
    size,
    pairwise: measure(hasDuplicatePairwise, values, iterations),
    withSet: measure(hasDuplicateWithSet, values, iterations),
  });
}

Dữ liệu không trùng kích hoạt trường hợp xấu nhất của cả hai ứng viên. Cần thử thêm phần tử trùng ở đầu và cuối, giá trị lệch cùng kích thước production. Dữ liệu ngẫu nhiên nên có seed. Thuật toán làm thay đổi đầu vào cần bản sao mới ngoài vùng đo hoặc setup tương đương cho mọi ứng viên.

Median giảm ảnh hưởng của lần dừng bất thường nhưng không cho thấy tail behavior. Khi latency quan trọng, hãy ghi phân phối và percentile. Cô lập process, cố định runtime, ghi phần cứng và so sánh confidence interval nếu chênh lệch nhỏ. Tách benchmark end-to-end khỏi algorithmic kernel; không được tính I/O cho chỉ một ứng viên.

Hãy nhìn đường cong thay vì một con số: thử các kích thước tăng dần và tìm slope hoặc crossover point. Nếu gấp đôi nn làm thời gian tăng gần bốn lần, thành phần bậc hai có thể đang chi phối. Profiler, allocation trace, database plan và hardware counter giúp giải thích nguyên nhân.

Ra quyết định và lưu lại các giả định

Lựa chọn thuật toán trong thực tế là bài toán ràng buộc. Bắt đầu từ tính đúng đắn, rồi xác định kích thước đầu vào dự kiến và tối đa, mục tiêu latency cùng throughput, giới hạn bộ nhớ, tần suất cập nhật và khả năng đầu vào mang tính đối kháng. Suy ra cận cho các thao tác chi phối workflow. Loại ứng viên có tốc độ tăng không thể đáp ứng ràng buộc. Benchmark các ứng viên còn lại trong runtime thật với dữ liệu đại diện.

Đôi khi đáp án đúng lại rất đơn giản. Quét tuyến tính có thể rõ ràng và nhanh hơn cho collection bị giới hạn ở hai mươi phần tử. Sắp xếp một lần rồi binary search có thể thắng khi số lần đọc lớn hơn nhiều số lần ghi. Hash table phù hợp cho membership check thường xuyên, còn mảng đã sắp xếp có thể tốn ít bộ nhớ hơn và duyệt nhanh hơn. External sort là lựa chọn hợp lý khi dữ liệu không nằm vừa trong RAM, dù mô hình I/O của nó không xuất hiện trong bảng Big-O cơ bản.

Hãy ghi giả định cạnh quyết định: “Tối đa 5.000 record cho mỗi tenant,” “key không do kẻ tấn công kiểm soát,” hoặc “mảng được dựng lại một lần và truy vấn hàng triệu lần.” Những phát biểu này giá trị hơn một nhãn độ phức tạp đứng riêng, vì hệ thống giám sát có thể phát hiện khi chúng không còn đúng.

Các điểm cần ghi nhớ:

  • Big-O, Big-Omega và Big-Theta biểu diễn cận tăng trưởng trên, dưới và chặt; chúng không đo số giây.
  • Phân tích xấu nhất, trung bình và khấu hao trả lời các câu hỏi khác nhau, không thể dùng thay thế cho nhau.
  • Định nghĩa mọi biến đầu vào, đồng thời nêu cách biểu diễn, thao tác, mô hình xác suất và tài nguyên đang phân tích.
  • Phân tích bộ nhớ phụ trợ, độ sâu stack, peak live memory, I/O và lời gọi từ xa song song với thời gian CPU.
  • Hằng số, cache locality, allocation và branch behavior quyết định người thắng trong miền đầu vào hệ thống thực sự vận hành.
  • Benchmark workload đã warm up, có tiêu thụ kết quả, tái lập được trên nhiều kích thước; xem phân phối thay vì tin một phép đo.
  • Chọn thuật toán đơn giản nhất đáp ứng ràng buộc đã đo, đồng thời lưu các giả định làm cho lựa chọn đó hợp lệ.

Bảng tra cứu chỉ là chú giải bản đồ, không phải địa hình thật. Kỹ thuật phần mềm bắt đầu khi mỗi nhãn trở thành một khẳng định rõ ràng mà code, workload và phép đo đều có thể phản biện.