Mỗi mức xử lí tổng cộng khoảng n phần tử
Với dãy có n phần tử, hai lời gọi sắp xếp hai nửa đều cần được tính. Bước trộn hai kết quả mất O(n). Khi n chẵn, có thể viết công thức truy hồi:
$$T(n)=2T(n/2)+O(n).$$
Chia đôi liên tiếp tạo khoảng log₂n mức. Ở mỗi mức, tổng độ dài các đoạn là n, nên công việc trộn ở mức đó là O(n). Tổng qua các mức là **O(n log n)**. Với n lẻ, hai nửa lệch nhau một phần tử và kết luận về bậc vẫn giữ nguyên.
Mã Python dùng lát cắt cũng cần thời gian chép dữ liệu. Phần chép vẫn tuyến tính theo độ dài mỗi mức và không làm đổi bậc O(n log n). Chỉ có độ sâu log n không đủ để kết luận toàn thuật toán O(log n).
Tính theo một quy ước đơn giản
Để minh họa cách cộng hai nhánh, quy ước T(1)=1; với n là lũy thừa của 2, mỗi lần gọi không cơ sở tốn 2 đơn vị kiểm/chia và n đơn vị trộn. Khi đó T(n)=2T(n/2)+n+2.
| Kích thước | Tính theo quy ước | Số đơn vị |
|---|---|---|
| 1 | Cơ sở | 1 |
| 2 | 2×1+2+2 | 6 |
| 4 | 2×6+4+2 | 18 |
Đây là mô hình quy ước để hiểu công thức, không phải số giây hoặc tổng số lệnh Python đã đo. Bậc O(n log n) tăng chậm hơn O(n²) khi n lớn, nhưng không bảo đảm mỗi lần chạy trên dãy nhỏ đều nhanh hơn sắp xếp chèn; cần đo trên dữ liệu thật trong cùng điều kiện.
Bài luyện
Công thức nào thể hiện đúng hai nửa và bước trộn?
Đây chỉ tính một nhánh với công việc ngoài nhánh hằng số.
Hai phần có kích thước khoảng n/2, không phải n−1.
Sắp xếp phải xử lí dữ liệu của dãy.
Có hai bài toán nhỏ và một bước trộn tuyến tính.
Lời giải
Hai lời gọi đệ quy cộng thành 2T(n/2); bước trộn tổng độ dài n tốn O(n). Cộng hai phần nhận công thức đã nêu.
Bài luyện
Theo quy ước T(1)=1,T(n)=2T(n/2)+n+2, T(4) bằng bao nhiêu?
T(2)=6 nên T(4)=2×6+4+2=18.
6 là T(2).
Chưa cộng bước kiểm/chia và trộn ở mức4.
Đơn vị mô hình chưa phải giây đã đo.
Lời giải
T(2)=2×T(1)+2+2=6. Do đó T(4)=2×6+4+2=18 đơn vị theo quy ước; không thể đổi thẳng thành giây chạy máy.
Bài luyện
Vì sao toàn bộ sắp xếp trộn có O(n log n), không phải chỉ O(log n)?
Trộn hai kết quả là bước cần thiết.
Phải tính tổng công việc của mọi đoạn, không chỉ độ sâu.
Mọi đoạn của mức đều cần xử lí.
Cả hai nửa đều được sắp xếp.
Lời giải
Độ sâu khoảng log n. Ở một mức, cộng công việc trộn của tất cả các đoạn được O(n). Nhân số mức cho công việc mỗi mức nhận O(n log n).
Đang học