Độ phức tạp thuật toán và Big O notation trong Python
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
Trong bài này · 12
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.
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 1000Số 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.
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 499500Số 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.
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 1000O(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.
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 19Dữ 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
Sau
n = 20,buoc = 0vàfor i in range(n): buoc += n, lệnhprint(buoc)in ra gì?2040040
Hàm
so_lan_chia_doi(n)của bài trả về bao nhiêu vớin = 64?- 6
- 32
- 64
Với list
dsvà sets, mỗi nhóm cónphầ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 dsx in s
Trong khung bẫy đo trên dữ liệu dễ, hàm
trung_hai_vongtrả 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
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_mamộ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.
def ma_lap_lai(cac_ma):
pass # Viết thân hàm thay cho dòng nàyTó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
nphầ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ònintrê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
intrê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ủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
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.