Login

Độ phức tạp thuật toán và ký hiệu Big O: giải thích dễ hiểu

  • author-image

    Nguyễn Đình Cường

  • blog-tag
  • blog-comment 0 comment
  • created-date 09 Nov, 2026
blog-thumbnail

Hai đoạn code cùng cho kết quả đúng, nhưng một đoạn chạy trong chớp mắt còn đoạn kia làm máy treo khi dữ liệu lớn. Big O là ngôn ngữ để nói về sự khác biệt đó mà không cần đo đồng hồ.

Big O đo cái gì?

Big O mô tả tốc độ tăng của số bước thực hiện khi kích thước dữ liệu n tăng. Nó không đo giây cụ thể, vì thời gian phụ thuộc máy móc. Thay vào đó, ta xem khi dữ liệu gấp đôi, gấp mười thì công việc tăng bao nhiêu. Có hai loại: độ phức tạp thời gian và độ phức tạp bộ nhớ.

Các mức thường gặp

Ký hiệuTênVí dụ
O(1)Hằng sốLấy phần tử mảng theo chỉ số
O(log n)LogaritTìm kiếm nhị phân
O(n)Tuyến tínhDuyệt hết mảng một lần
O(n log n)Gần tuyến tínhSắp xếp hiệu quả (merge sort)
O(n^2)Bình phươngHai vòng lặp lồng nhau
O(2^n)MũThử mọi tập con

Thứ tự từ nhanh đến chậm cũng chính là thứ tự trong bảng. O(1) và O(log n) gần như không đáng lo; từ O(n^2) trở đi dữ liệu lớn sẽ gây vấn đề.

Cách xác định Big O qua ví dụ

# O(1): số bước không đổi
def phan_tu_dau(ds):
    return ds[0]

# O(n): duyệt một lần
def tong(ds):
    t = 0
    for x in ds:
        t += x
    return t

# O(n^2): hai vòng lồng nhau
def co_trung(ds):
    for i in range(len(ds)):
        for j in range(i + 1, len(ds)):
            if ds[i] == ds[j]:
                return True
    return False

# O(n): cải tiến bằng set
def co_trung_nhanh(ds):
    da_thay = set()
    for x in ds:
        if x in da_thay:
            return True
        da_thay.add(x)
    return False

Hai hàm cuối cùng làm cùng một việc. Với 1.000 phần tử, bản đầu có thể cần cỡ nửa triệu phép so sánh, bản sau chỉ cỡ một nghìn bước. Với một triệu phần tử, chênh lệch là khổng lồ. Đây chính là giá trị thực tế của việc hiểu Big O, kết hợp với cấu trúc dữ liệu đúng.

Quy tắc rút gọn

  1. Bỏ hằng số: O(3n) viết là O(n), vì ta quan tâm xu hướng tăng.
  2. Giữ số hạng lớn nhất: O(n^2 + n) viết là O(n^2).
  3. Vòng lặp lồng nhau thì nhân, vòng lặp nối tiếp thì cộng.
  4. Mỗi lần chia đôi dữ liệu thường cho ra log n.

Đánh đổi thời gian và bộ nhớ

Thường bạn có thể đổi bộ nhớ lấy tốc độ. Hàm co_trung_nhanh dùng thêm một set, tốn O(n) bộ nhớ nhưng nhanh hơn nhiều. Kỹ thuật ghi nhớ kết quả (memoization) trong đệ quy cũng là ví dụ khác. Không có lựa chọn tốt tuyệt đối, bạn cân nhắc theo bài toán.

Đừng tối ưu quá sớm

Big O không có nghĩa là lúc nào cũng phải viết thuật toán tối ưu nhất. Với danh sách vài chục phần tử, O(n^2) vẫn chạy tức thì và code đơn giản dễ đọc hơn. Hãy viết cho đúng và rõ ràng trước; khi đo thấy chậm, hoặc khi biết chắc dữ liệu sẽ lớn, mới tối ưu đúng chỗ nghẽn.

Bảng ước lượng: dữ liệu bao nhiêu thì chịu được?

Một quy tắc kinh nghiệm: máy tính thông thường xử lý được vào cỡ hàng chục triệu phép tính đơn giản mỗi giây trong ngôn ngữ thông dịch, nhiều hơn trong ngôn ngữ biên dịch. Con số này chỉ là ước lượng thô nhưng đủ để định hướng:

Độ phức tạpn khoảng 1.000n khoảng 1.000.000
O(n)Tức thìVẫn ổn
O(n log n)Tức thìVẫn ổn
O(n^2)ỔnRất chậm, có thể hàng giờ
O(2^n)Không khả thiKhông khả thi

Vì vậy trong các bài thi lập trình, người ta thường nhìn giới hạn của n để đoán thuật toán cần dùng. Trong công việc, bạn nên đo thực tế bằng công cụ đo thời gian trước khi tối ưu:

import time

t = time.perf_counter()
co_trung(list(range(3000)))
print(round(time.perf_counter() - t, 3), "giây")

Thử với n tăng dần để tận mắt thấy đường cong O(n^2) dựng đứng như thế nào.

Bài tập

Xác định độ phức tạp của: tìm phần tử lớn nhất (O(n)), kiểm tra danh sách có trùng bằng hai vòng lặp (O(n^2)), in mọi cặp (a, b) trong hai danh sách (O(n x m)), và đếm số bit của n bằng cách chia đôi liên tục (O(log n)).

Kết luận

Big O cho bạn một cách nhanh để ước lượng code có "chịu được" dữ liệu lớn hay không. Hãy tập thói quen nhìn vòng lặp và tự hỏi: số bước phụ thuộc n như thế nào? Chỉ cần nhận ra các mức O(1), O(log n), O(n), O(n^2) là bạn đã đi được một nửa đường.

Bạn có thể tiếp tục hành trình với những khóa học lập trình trên codebem.com, học theo tốc độ của riêng mình.

author_photo
Nguyễn Đình Cường

0 comment