Chuyển tới nội dung chính

Big-O vs Big-Θ vs Big-Ω

Bạn sẽ học được gì

Cùng một thuật toán có thể nhanh hay chậm tùy dữ liệu may hay xui. Bài này phân biệt ba ký hiệu: O (xấu nhất), Ω (tốt nhất), Θ (chặt — khi tốt và xấu cùng cỡ), và vì sao trong thực tế người ta hay quan tâm xấu nhất.

1. Trực quan: tìm tên trong danh sách CHƯA sắp xếp​

Bạn dò từ đầu danh sách n người để tìm "Phúc":

  • May (tốt nhất): Phúc đứng đầu → tìm thấy ngay bước 1. Chỉ 1 thao tác.
  • Xui (xấu nhất): Phúc đứng cuối, hoặc không có → phải dò hết n người.
  • Trung bình: thường thấy ở khoảng giữa → ~n/2 thao tác.

Cùng một thuật toán, nhưng số thao tác dao động từ 1 tới n tùy dữ liệu. Ba ký hiệu sinh ra để nói chính xác ta đang bàn trường hợp nào.

2. Ba ký hiệu​

Ký hiệuTênNghĩaTrả lời câu hỏi
O(...)Big-Ocận trên — không tệ hơn mức này"Xấu nhất thì chậm cỡ nào?"
Ω(...)Big-Omegacận dưới — không nhanh hơn mức này"Tốt nhất thì nhanh cỡ nào?"
Θ(...)Big-Thetacận chặt — kẹp cả trên lẫn dưới"Cỡ nào là đúng?" (khi trên = dưới)

Với tìm tuyến tính ở trên:

  • O(n) — xấu nhất phải quét hết.
  • Ω(1) — tốt nhất trúng ngay phần tử đầu.
  • Không có một Θ chung cho mọi trường hợp vì tốt nhất (1) và xấu nhất (n) khác cỡ nhau.
Khi nào có Θ?

Khi tốt nhất và xấu nhất cùng cỡ. Ví dụ "tính tổng mảng" luôn phải duyệt hết n phần tử dù dữ liệu thế nào → tốt nhất = xấu nhất = n → Θ(n) (và cũng là O(n), Ω(n)).

3. Chạy debug: thấy "may" và "xui" khác nhau​

Cùng thuật toán tìm tuyến tính, hai dữ liệu khác nhau. Để ý số bước (buoc):

🐞 Tìm 7 trong [7, 2, 9, 4] — trường hợp MAYBước 1/2
1def tim(A, muc_tieu):
2  for i in range(len(A)):
3      if A[i] == muc_tieu:
4          return i
5  return -1
Biến tại bước này
i0
buoc1
👉 Xét A[0] = 7.
🐞 Tìm 4 trong [7, 2, 9, 4] — trường hợp XUIBước 1/4
1def tim(A, muc_tieu):
2  for i in range(len(A)):
3      if A[i] == muc_tieu:
4          return i
5  return -1
Biến tại bước này
i0
buoc1
👉 A[0] = 7, không phải 4.

Cùng code, cùng mảng, chỉ khác phần tử cần tìm — một bên 1 bước, một bên n bước.

4. Vì sao thực tế hay nói "xấu nhất"?​

Khi nói "thuật toán này O(n)", đa số ngầm hiểu là trường hợp xấu nhất. Lý do: ta cần bảo đảm — biết chắc nó không bao giờ tệ hơn mức nào, để hệ thống không bất ngờ treo khi gặp dữ liệu xui. "Tốt nhất" thì vui nhưng không đáng tin để lập kế hoạch.

Một ví dụ kinh điển: quick sort có xấu nhất O(n²) (khi chọn pivot dở) nhưng trung bình Θ(n log n). Người ta dùng nó vì trung bình rất tốt, đồng thời biết rõ rủi ro xấu nhất để phòng.

5. Mẫu nhận diện​

  • Có return/break sớm giữa chừng → tốt nhất và xấu nhất thường khác nhau (có Ω riêng, O riêng).
  • Luôn duyệt hết dù thế nào (tổng, max, đếm) → tốt nhất = xấu nhất → có Θ rõ ràng.
  • Khi không nói rõ, "Big-O" ≈ "xấu nhất".

6. 🎮 Trò chơi: Tốt nhất hay xấu nhất?​

🎮 Tốt nhất hay xấu nhất?Câu 1/4· Điểm 0· 🔥 0

Với tìm tuyến tính (dò từ đầu) trên n phần tử, chọn độ phức tạp đúng cho từng tình huống.

Khi ai đó nói "thuật toán này là O(n²)" mà không nói gì thêm, họ thường ngụ ý?

7. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Ký hiệu nào mô tả CẬN TRÊN (xấu nhất)?
2. Khi nào một thuật toán có Θ rõ ràng?
3. Tìm tuyến tính trên mảng n phần tử, trường hợp tốt nhất là?

8. Hoàn thành​

…

☑️ Tiếp theo: 1.2.5 — Độ phức tạp không gian (đo bộ nhớ, không chỉ thời gian).