Ước lượng công việc để chọn thuật toán

Lan cần tính tổng số vé đánh số từ 1 đến n. Với 10 vé, cộng từng số cho kết quả ngay. Khi n lên đến một tỷ, cô muốn biết cách nào vẫn kịp hoàn thành.

Cùng một kết quả có thể cần lượng công việc khác nhau

Với n = 10, Lan thử cộng từng số và đếm số lần cộng. Sau đó bạn ấy tính tổng bằng cách ghép số đầu với số cuối:

n = 10
total = 0
steps = 0
for value in range(1, n + 1):
    total += value
    steps += 1
formula = n * (n + 1) // 2
print("Tổng bằng vòng lặp:", total)
print("Số lần cộng:", steps)
print("Tổng bằng công thức:", formula)

Tổng bằng vòng lặp: 55
Số lần cộng: 10
Tổng bằng công thức: 55

Hai tổng bằng nhau, còn số lần cộng trong vòng lặp bằng n. Công thức đúng vì ghép số thứ nhất với số cuối cho tổng n + 1. Ghép theo cả hai chiều đếm mỗi số hai lần, nên chia kết quả cho 2.

Nếu n = 10^9, cách lặp thực hiện một tỷ lần cộng. Công thức chỉ dùng một số phép tính số học cố định. Phép chia // cho kết quả nguyên chính xác ở đây vì n * (n + 1) luôn chẵn.

Một chương trình có thể in đúng với ví dụ nhưng nhận quá thời gian (Time Limit Exceeded, hay TLE) ở dữ liệu lớn. Bài 1 giới thiệu cách đọc kết quả chấm. Ở đây bạn ước lượng lượng việc trước khi chọn cách giải.

Big-O mô tả tốc độ tăng thay vì số giây

Độ phức tạp thời gian (time complexity) mô tả lượng thao tác theo kích thước đầu vào. Với một danh sách, n thường là số phần tử. Chọn thao tác cần đếm, chẳng hạn phép so sánh, trước khi tính số lần.

Ký hiệu Big-O cho một cận trên theo tốc độ tăng khi đầu vào lớn. Nếu số thao tác nhiều nhất là 3n + 2, ta có thể viết O(n). Ký hiệu này không cho số giây chính xác và không có nghĩa mọi đầu vào đều cần cùng số thao tác.

Chương trình sau đếm phép cộng trong hai vòng nối tiếp và một vòng lồng nhau. Hãy so sánh khi n tăng từ 4 lên 8:

for n in (4, 8):
    sequential = 0
    nested = 0
    for i in range(n):
        sequential += 1
    for j in range(n):
        sequential += 1
    for i in range(n):
        for j in range(n):
            nested += 1
    print(n, sequential, nested)

4 8 16
8 16 64

Hai vòng nối tiếp cho 2n lần đếm nên thuộc O(n). Vòng lồng nhau cho n * n lần đếm nên thuộc O(n^2). Khi n tăng gấp đôi, số lần ở vòng lồng tăng gấp bốn.

Bảng sau được tạo bằng chương trình. Cột chia đôi đếm số lần chia nguyên cho 2 để về 1:

Đây là số thao tác theo mô hình đã chọn, không phải thời gian đo bằng giây. Một phép tính số lớn, một lần đọc dữ liệu và một phép so sánh có thể tốn thời gian khác nhau. Máy, ngôn ngữ và giới hạn chấm cũng ảnh hưởng đến kết quả.

Đếm vòng lặp theo số lần thật sự thực hiện

Tuyến tính (linear), viết O(n), thường xuất hiện khi duyệt một lượt. Ở ví dụ sau, ta tìm giá trị lớn nhất của bốn số. Dãy không rỗng nên có thể lấy phần tử đầu làm giá trị ban đầu:

a = [-7, 5, 5, -2]
best = a[0]
comparisons = 0
for value in a[1:]:
    comparisons += 1
    if value > best:
        best = value
print("Lớn nhất:", best)
print("Số lần so sánh:", comparisons)

Lớn nhất: 5
Số lần so sánh: 3

Có ba lần so sánh vì phần tử đầu đã dùng để khởi tạo. Duyệt hết đảm bảo mọi phần tử đều đã được xét. Với n phần tử, số so sánh là n - 1, thuộc O(n); ngoài dữ liệu đầu vào chỉ cần vài biến.

Bậc hai (quadratic), viết O(n^2), xuất hiện khi phải xét mọi cặp vị trí. Đoạn sau chỉ xét cặp có vị trí đầu nhỏ hơn vị trí sau:

for n in (4, 8):
    pairs = 0
    for i in range(n):
        for j in range(i + 1, n):
            pairs += 1
    print(n, pairs, n * (n - 1) // 2)

4 6 6
8 28 28

Mỗi cặp có đúng một thứ tự chỉ số nhỏ trước, lớn sau. Có n * (n - 1) / 2 cặp, nên cách đếm vẫn thuộc O(n^2). Với n = 200000, con số này là gần 20 tỷ, dù ít hơn n^2 một nửa.

Hai vòng lồng nhau không tự động là O(n^2). Nếu vòng trong chạy đúng ba lần, tổng chỉ là 3n, tức O(n). Khi kích thước khác nhau, giữ cả hai biến: duyệt bảng n hàng và m cột là O(nm).

n = 5
count = 0
for row in range(n):
    for column in range(3):
        count += 1
print("Số ô:", count)

Số ô: 15

Vòng trong cố định ba lần, nên số ô tăng gấp đôi khi số hàng tăng gấp đôi. Nếu số cột cũng tăng theo n, cần tính lại thành n * m. Không thay m bằng n khi đề chưa nói hai kích thước bằng nhau.

Chia đôi liên tiếp tạo ra số bước logarithm

Logarithm (logarithm) ở đây có thể hiểu là số lần chia đôi đến khi còn rất ít. Với 8 khả năng, mỗi lần giảm một nửa, chỉ sau 3 bước là còn đúng một khả năng:

Hình chỉ minh họa khi ta có quy tắc chắc chắn loại được nửa còn lại. Không thể tùy ý bỏ một nửa danh sách chưa sắp xếp. Đoạn sau đếm số lần chia đôi của các kích thước khác nhau:

for size in (8, 64, 1000000):
    remaining = size
    steps = 0
    while remaining > 1:
        remaining //= 2
        steps += 1
    print(size, steps)

8 3
64 6
1000000 19

Mỗi bước giữ không quá một nửa lượng cũ. Vì 2^20 lớn hơn một triệu, số lần chia ở ví dụ rất nhỏ so với một triệu. Số bước này thuộc O(log n); đổi cơ số logarithm chỉ đổi một hệ số cố định.

Trong tìm kiếm nhị phân (binary search), danh sách phải có thứ tự phù hợp. Đoạn sau tìm một số trong danh sách tăng dần bằng khoảng [left, right):

a = [2, 4, 7, 9, 12, 15, 18, 21]
target = 12
left, right = 0, len(a)
checks = 0
while left < right:
    mid = (left + right) // 2
    checks += 1
    if a[mid] < target:
        left = mid + 1
    else:
        right = mid
print("Vị trí:", left)
print("Tìm thấy:", left < len(a) and a[left] == target)
print("Số lần so sánh ở vòng lặp:", checks)

Vị trí: 4
Tìm thấy: True
Số lần so sánh ở vòng lặp: 3

Nếu phần tử giữa nhỏ hơn đích, mọi phần tử bên trái nó cũng nhỏ hơn đích. Nếu không, vị trí cần tìm không nằm bên phải phần tử giữa. Khoảng tìm kiếm thu hẹp cho đến khi còn vị trí đầu có giá trị không nhỏ hơn đích.

Khi đích lớn hơn mọi phần tử, left bằng độ dài danh sách. Điều kiện ngắn mạch kiểm tra giới hạn trước khi truy cập, nên không gây lỗi chỉ số. Một lần tìm tốn O(log n) sau khi đã có danh sách được sắp xếp; chi phí sắp xếp phải được tính riêng.

Cộng chi phí các bước và tính thêm bộ nhớ

Giả sử cần sắp xếp n điểm rồi duyệt một lượt. Sắp xếp dùng O(n log n) trong trường hợp xấu nhất; lượt duyệt thêm O(n). Tổng thuộc O(n log n), không phải O(n^2) vì hai công đoạn nối tiếp.

scores = [8, 4, 9, 6, 6]
scores.sort()
passed = 0
for score in scores:
    if score >= 6:
        passed += 1
print("Điểm đã xếp:", scores)
print("Số điểm đạt:", passed)

Điểm đã xếp: [4, 6, 6, 8, 9]
Số điểm đạt: 4

Mọi điểm được kiểm tra sau khi xếp, nên số điểm đạt không phụ thuộc thứ tự ban đầu. Tuy nhiên, nếu chỉ cần đếm, có thể duyệt trực tiếp trong O(n). Không nên sắp xếp chỉ vì công cụ có sẵn.

Bộ nhớ phụ (auxiliary space) là bộ nhớ tăng thêm ngoài dữ liệu vào và kết quả theo quy ước phân tích. Duyệt để tính tổng chỉ giữ một biến tích lũy, tức O(1) biến phụ. Tạo danh sách bản sao có n phần tử cần O(n) bộ nhớ phụ.

a = [3, 1, 4, 1]
total = 0
for value in a:
    total += value
copy = [value for value in a]
print("Tổng:", total)
print("Số phần tử bản sao:", len(copy))

Tổng: 9
Số phần tử bản sao: 4

Ở đây số phần tử trong bản sao tăng theo kích thước đầu vào. Số biến trong cách cộng không tăng theo số phần tử. Kích thước từng số nguyên Python cũng có thể tăng, nên O(1) phép toán số học là mô hình khi giá trị vừa phạm vi đề.

Thời gian đọc và in cũng cần tính. Nếu đầu vào chứa n số, riêng việc đọc toàn bộ đã phải xử lý lượng dữ liệu tăng theo độ dài văn bản. Một công thức trả lời từ một số n khác với việc phải đọc n số được liệt kê.

Số tập con và hoán vị tăng rất nhanh

Với mỗi vật, có hai lựa chọn: lấy hoặc không lấy. Do đó n vật phân biệt có 2^n tập con, kể cả tập rỗng. Hàm mũ (exponential) tăng nhanh hơn đa thức khi n đủ lớn.

Nếu xếp n vật phân biệt thành hàng, có n! cách. Số này là tích từ 1 đến n, gọi là giai thừa (factorial). Đoạn sau tính số lựa chọn chứ không sinh tất cả chúng:

from math import factorial
for n in (5, 10, 15, 20):
    print(n, 2 ** n, factorial(n))

5 32 120
10 1024 3628800
15 32768 1307674368000
20 1048576 2432902008176640000

Với 20 vật đã có hơn một triệu tập con, còn số cách xếp lớn hơn rất nhiều. Nếu mỗi tập con cần duyệt thêm n vật, chi phí là O(n * 2^n), không chỉ O(2^n). Bài 3 sẽ đi sâu cách duyệt và kiểm tra từng lựa chọn.

Đọc giới hạn trước khi chọn cách giải

Một ràng buộc (constraint) cho biết những đầu vào hợp lệ, không bảo đảm một thuật toán cụ thể sẽ chạy kịp. Hãy tính theo giá trị lớn nhất, tổng số bộ dữ liệu, lượng đọc và lượng in. Sau đó đo trên môi trường chấm nếu có thể.

Các mốc dưới đây chỉ là gợi ý chọn hướng, không phải giới hạn thời gian cố định:

Bảng không thay thế đo đạc. Dữ liệu gồm một số n = 10^9 có độ dài ngắn, nhưng danh sách một tỷ số rất lớn. Cần phân biệt giá trị của n với số phần tử thực sự phải đọc.

Tìm cặp có tổng cho trước bằng ba cách

Giả sử một cửa hàng có các giá [4, 1, 7, 4] và cần hai món ở hai vị trí khác nhau có tổng 8. Hai món giá 4 hợp lệ vì chúng ở hai vị trí khác nhau. Giá trị âm và các giá trị trùng vẫn cần được xử lý nếu đề cho phép.

Cách đầu tiên xét mọi cặp i < j:

a = [4, 1, 7, 4]
target = 8
found = False
checks = 0
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        checks += 1
        if a[i] + a[j] == target:
            found = True
print("Có cặp:", found)
print("Cặp đã xét:", checks)

Có cặp: True
Cặp đã xét: 6

Vì mỗi cặp chỉ số khác nhau đều xuất hiện đúng một lần, cách này tìm đủ các cặp. Nếu không dừng sớm, nó xét n(n - 1)/2 cặp và dùng O(n^2) thời gian. Đây là cách đối chiếu tốt trên dữ liệu nhỏ.

Cách thứ hai sắp xếp bản sao rồi đặt hai con trỏ ở hai đầu. Con trỏ là chỉ số cho biết vị trí đang xét:

a = [4, 1, 7, 4]
target = 8
b = sorted(a)
left, right = 0, len(b) - 1
found = False
while left < right:
    current = b[left] + b[right]
    if current == target:
        found = True
        break
    if current < target:
        left += 1
    else:
        right -= 1
print("Danh sách đã xếp:", b)
print("Có cặp:", found)

Danh sách đã xếp: [1, 4, 4, 7]
Có cặp: True

Nếu tổng quá nhỏ, ghép phần tử bên trái với vị trí nào còn lại cũng không lớn hơn tổng đang xét. Vì vậy có thể bỏ vị trí trái đó. Nếu tổng quá lớn, lập luận đối xứng cho phép bỏ vị trí phải.

Điều kiện left < right đảm bảo không dùng cùng một vị trí hai lần. Sắp xếp tốn O(n log n), còn hai con trỏ dịch tổng cộng không quá n lần. Bản sao cần O(n) bộ nhớ; thứ tự ban đầu không bị thay đổi.

Cách thứ ba lưu các giá trị đã đi qua vào tập hợp (set). Với mỗi số, ta tìm số bù trước rồi mới thêm số hiện tại:

a = [4, 1, 7, 4]
target = 8
seen = set()
found = False
for value in a:
    if target - value in seen:
        found = True
        break
    seen.add(value)
print("Có cặp:", found)
print("Các giá trị đã lưu:", sorted(seen))

Có cặp: True
Các giá trị đã lưu: [1, 4]

Nếu tìm thấy số bù trong seen, nó đến từ một vị trí trước vị trí hiện tại. Ngược lại, khi có cặp hợp lệ, phần tử xuất hiện sau sẽ tìm thấy phần tử trước. Kiểm tra trước khi thêm tránh dùng một phần tử hai lần.

Với bảng băm hoạt động như thường kỳ vọng, cách này tốn O(n) thời gian trung bình và tối đa O(n) phần tử lưu thêm. Đây không phải bảo đảm thời gian xấu nhất cho mọi dữ liệu và mọi triển khai. Nếu cần chỉ số gốc, phải lưu thêm thông tin vị trí.

Kiểm tra giả định trước khi tin phép ước lượng

Một lời giải nhanh nhưng sai vẫn không đạt. Bạn cần kiểm tra ít nhất dữ liệu nhỏ nhất, các giá trị bằng nhau, giá trị âm nếu được phép, và trường hợp không có đáp án. Với tổng cặp, một số duy nhất không thể tạo thành cặp hai vị trí.

a = [4]
target = 8
seen = set()
found = False
for value in a:
    if target - value in seen:
        found = True
    seen.add(value)
print("Có cặp:", found)

Có cặp: False

Nếu thêm 4 trước khi kiểm tra, chương trình có thể tự ghép số đó với chính nó. Trường hợp một phần tử phát hiện sai lầm này ngay. Thử thêm dữ liệu lớn sau khi đã xác nhận tính đúng trên dữ liệu nhỏ.

Thời gian chạy thực tế có thể thay đổi giữa các lần chạy và máy khác nhau. Việc đếm số thao tác cho thấy xu hướng, còn phép đo trong môi trường chấm giúp kiểm tra giới hạn cụ thể. Một ví dụ nhỏ không chứng minh được tốc độ ở giới hạn lớn.

Lỗi thường gặp

Tóm tắt

• Chọn kích thước đầu vào và thao tác cần đếm trước khi phân tích.
• Vòng nối tiếp cộng chi phí; vòng lồng cần tính số lần thực hiện thực tế.
• Chia đôi liên tiếp thường cho O(log n); sắp xếp thường tốn O(n log n).
• Đọc giới hạn, chi phí vào ra và bộ nhớ trước khi quyết định một hướng giải.
• Chứng minh tính đúng rồi thử dữ liệu biên và dữ liệu lớn.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về sắp xếp giải thích cách dùng sort và sorted.
• Tài liệu Python về kiểu tập hợp mô tả thao tác với set.