Bỏ qua đến nội dung chính
Mục lục

Độ phức tạp thuật toán và Big O notation trong Python

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 2/20 · Chương 23

Cấu trúc dữ liệu và giải thuật

  • 8 phút
  • Trung cấp
  • Python 3.14
  • Cập nhật

Ký hiệu O lớn (Big O notation) là cách viết gọn độ phức tạp thuật toán: số bước của một đoạn code tăng nhanh tới đâu khi dữ liệu lớn lên. Bạn cần nó khi một hàm chạy tốt với 10 khách trong hàng chờ nhưng phải phục vụ cả một triệu khách, và muốn biết trước nó có trụ được không.

Cần biết trước: vòng lặp lồng nhau, toán tử in và lệnh return.

Đếm số bước thay cho bấm giờ

Bấm giờ một hàm cho ra con số khác nhau trên máy nhanh, máy chậm, lúc máy rảnh và lúc máy bận. Số bước thì không đổi: bạn đếm số phép so sánh hay số lần tra mà hàm làm, theo số phần tử n. Hàm dưới đây tìm thời gian chờ lâu nhất trong hàng và tự đếm số lượt nó xét.

python
def lau_nhat(phut_cho):
    buoc = 0
    lon_nhat = phut_cho[0]
    for phut in phut_cho:
        buoc += 1
        if phut > lon_nhat:
            lon_nhat = phut
    return lon_nhat, buoc

for n in [10, 100, 1000]:
    phut_cho = list(range(n))
    print(n, lau_nhat(phut_cho)[1])

KẾT QUẢ

10 10
100 100
1000 1000

Số bước bằng đúng n: list dài gấp 10 thì việc cũng gấp 10. Độ phức tạp của hàm là quy luật tăng đó, và Big O viết nó là O(n), đọc là "O của n". Ký hiệu chỉ giữ phần lớn nhanh nhất: hàm làm 2n + 3 bước vẫn là O(n), vì khi n lên một triệu thì hệ số 2 và số 3 không đổi được bức tranh.

Vòng lặp lồng nhau cho O(n²)

Hỏi một list mã khách có hai mã trùng nhau không, cách thẳng là so từng cặp bằng hai vòng for lồng nhau. List không có mã trùng là trường hợp xấu nhất: hàm phải xét hết mọi cặp mới dám trả lời False.

python
def trung_hai_vong(ds):
    buoc = 0
    for i in range(len(ds)):
        for j in range(i + 1, len(ds)):
            buoc += 1
            if ds[i] == ds[j]:
                return True, buoc
    return False, buoc

for n in [10, 100, 1000]:
    print(n, trung_hai_vong(list(range(n)))[1])

KẾT QUẢ

10 45
100 4950
1000 499500

Số cặp là n * (n - 1) // 2. Khi n tăng 10 lần, số bước tăng khoảng 100 lần, nên độ phức tạp là O(n²), "O của n bình phương". Với một triệu mã, hàm cần khoảng 500 tỉ phép so sánh. Đổi [10, 100, 1000] thành [10, 100, 2000] rồi chạy lại: dòng cuối in 2000 1999000.

O(1): tra set và dict là một bước

Cũng câu hỏi đó, nhưng đi qua list một lượt và nhớ các mã đã gặp trong một set. Tài liệu chính thức của Python, trang "Time complexity of operations on built-in types" (docs.python.org/3/builtins/time-complexity.html, xem ngày 15/11/2026), ghi x in s trên set và tra khóa dict là O(1) tính trung bình, còn x in l trên list là O(n). Vì vậy mỗi lần tra set tính là một bước.

python
def trung_mot_luot(ds):
    da_gap = set()
    buoc = 0
    for x in ds:
        buoc += 1
        if x in da_gap:
            return True, buoc
        da_gap.add(x)
    return False, buoc

for n in [10, 100, 1000]:
    print(n, trung_mot_luot(list(range(n)))[1])

KẾT QUẢ

10 10
100 100
1000 1000

O(1) nghĩa là số bước không đổi dù nhóm lớn bao nhiêu. Lấy ds[i], gọi len(ds), append() (tính bình quân qua nhiều lần thêm) và tra d[k] cũng là O(1). Đổi hai vòng lồng nhau thành một lượt cộng một set, bạn đi từ O(n²) xuống O(n), với 1000 mã là từ 499.500 bước xuống 1000.

O(log n): mỗi bước bỏ một nửa

Tìm một tên trong danh bạ đã xếp theo chữ cái, bạn mở trang giữa, thấy tên cần tìm nằm ở nửa nào rồi bỏ nửa kia. Số bước khi đó là số lần chia đôi n cho tới khi còn một trang.

python
def so_lan_chia_doi(n):
    buoc = 0
    while n > 1:
        n = n // 2
        buoc += 1
    return buoc

for n in [10, 1000, 1_000_000]:
    print(n, so_lan_chia_doi(n))

KẾT QUẢ

10 3
1000 9
1000000 19

Dữ liệu tăng 1000 lần mà số bước chỉ thêm khoảng mười, nên độ phức tạp này là O(log n). Cách tìm bằng chia đôi đó là việc của bài tìm kiếm nhị phân. Bảng dưới đặt bốn mức cạnh nhau:

n

O(1)

O(log n)

O(n)

O(n²)

10

1

3

10

100

1.000

1

9

1.000

1.000.000

1.000.000

1

19

1.000.000

1.000.000.000.000

Muốn đo thời gian thật sau khi đã chọn được cách giải, bạn dùng module của bài profile và timeit.

Kiểm tra nhanh

  1. Sau n = 20, buoc = 0 và for i in range(n): buoc += n, lệnh print(buoc) in ra gì?

    • 20
    • 400
    • 40
  2. Hàm so_lan_chia_doi(n) của bài trả về bao nhiêu với n = 64?

    • 6
    • 32
    • 64
  3. Với list ds và set s, mỗi nhóm có n phần tử, những đoạn code nào làm O(n) bước?

    • for x in ds: print(x)
    • ds[0] + ds[-1]
    • x in ds
    • x in s
  4. Trong khung bẫy đo trên dữ liệu dễ, hàm trung_hai_vong trả về (True, 1) với list hơn 1000 mã. Kết luận nào đúng?

    • Hàm có độ phức tạp O(1)
    • Hàm chỉ chạy một bước với mọi list
    • Đó là trường hợp tốt nhất, phải đếm trên list không có mã trùng
Đúng hết lần đầu +15 XP

Bài tập

Tìm các mã khách quay lại trong một lượt

cac_ma là list mã khách theo thứ tự đến quầy trong ngày. Viết hàm ma_lap_lai(cac_ma) trả về các mã đến từ hai lần trở lên.

  • Mỗi mã có một lần trong kết quả, đặt theo thứ tự lần đến thứ hai của nó.

  • Hàm đi qua cac_ma một lượt, nhớ mã đã gặp trong set: trình chấm có một hàng đếm số phép so sánh và số lần tính mã băm với 1000 mã, và cách dò lại list sẽ trượt hàng đó.

  • Hàm không sửa cac_ma.

Ví dụ: ma_lap_lai([101, 102, 101, 103, 102, 101]) trả về [101, 102].

Trả về: các mã lặp lại, một list.

python
def ma_lap_lai(cac_ma):
    pass  # Viết thân hàm thay cho dòng này

Tóm tắt

  • Độ phức tạp đo số bước tăng theo n, không đo giây, và Big O chỉ giữ phần tăng nhanh nhất.

  • Một vòng lặp qua n phần tử là O(n), hai vòng lồng nhau so từng cặp là O(n²).

  • Tra set, tra khóa dict, lấy ds[i] là O(1) tính trung bình, còn in trên list là O(n).

  • Chia đôi phần còn lại ở mỗi bước cho O(log n): một triệu phần tử chỉ cần khoảng 20 bước.

  • Đếm bước trên trường hợp xấu nhất, và tính cả vòng lặp ngầm của in trên list.

Câu hỏi thường gặp

Big O là gì, giải thích cho người mới?

Big O là cách nói số bước của một giải thuật tăng theo quy luật nào khi dữ liệu lớn lên, bỏ qua hệ số và phần nhỏ. O(n) là tăng cùng nhịp với n, O(n²) là tăng theo bình phương. Bài cấu trúc dữ liệu và giải thuật cho thấy nó dùng ở đâu trong cả nhóm.

Độ phức tạp thuật toán là gì, có tính cả bộ nhớ không?

Có hai loại: độ phức tạp thời gian đếm số bước, độ phức tạp bộ nhớ đếm lượng chỗ cần thêm. Hàm trung_mot_luot() của bài nhanh hơn nhưng cần một set tới n phần tử, nên bộ nhớ thêm là O(n). Đổi bộ nhớ lấy tốc độ như vậy là chuyện thường gặp.

Vì sao in trên set nhanh hơn in trên list?

Set tính ra chỗ cất một giá trị ngay từ chính giá trị đó, nên đi thẳng tới đó thay vì so với từng phần tử. Bài toán tử in so hai cách này, còn bài bảng băm mở bên trong set và dict ra để bạn thấy cách tính chỗ cất.

O(1) có nghĩa là chỉ một bước không?

Không hẳn. O(1) nghĩa là số bước không tăng theo n: có thể là 1 bước hay 20 bước, miễn con số đó cố định. Chữ "trung bình" của set và dict cũng quan trọng: khi nhiều giá trị rơi vào cùng một chỗ cất, mỗi lần tra có thể chậm tới O(n).

Chủ đề

big o notation

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE

  • Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
  • Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
  • Xây hệ thống AI cho doanh nghiệp tại VietPlatform.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập