Các bậc tăng và chỗ chúng cắt nhau
Các bậc tăng và chỗ chúng cắt nhau
O(n²) có thật sự tệ hơn O(n) không? Câu trả lời là còn tùy n, và cái mốc quyết định thì bạn tính ra được bằng số nguyên chứ không phải đoán.
Ở bài đếm phép tính bạn đã đếm xem một đoạn mã chạy bao nhiêu lượt. Bước tiếp theo là gom các kết quả đếm ấy thành vài nhóm để dễ nói chuyện: 1, log₂ n, n, n log₂ n, n², n³, 2ⁿ, n!. Ký hiệu O chính là cái nhãn nhóm đó, và nó cố tình vứt đi hai thứ: hệ số nhân trước hàm, và mọi hằng cộng thêm.
Chỗ này gần như ai học lần đầu cũng hiểu lệch. O(n) không có nghĩa là "luôn nhanh hơn O(n²)". Nó chỉ nói: khi n đủ lớn thì đường n nằm dưới đường n². Còn "đủ lớn" là bao nhiêu thì O không nói, và câu trả lời phụ thuộc thẳng vào đúng hai con số mà O vừa ném đi. Có những bài toán mà "đủ lớn" lớn hơn mọi n bạn từng gặp trong đời, và khi đó cái thuật toán mang nhãn đẹp hơn lại là cái chậm hơn trên mọi dữ liệu thật.
Sim dưới đây cho bạn gõ thẳng hệ số vào. Mọi con số nó in ra đều là số học phổ thông trên đúng cấu hình bạn đặt, và hai chỗ khó nhất, tìm điểm cắt và xử lý số quá lớn, đều làm bằng số nguyên chính xác chứ không làm tròn.
1 · Tám bậc tăng và hệ số của chúng ✎ sửa được
Mỗi dòng là một hàm chi phí mult × f(n) + add. Ký hiệu O chỉ giữ lại cột bậc và ném hai cột hệ số đi. Đúng hai cột đó quyết định ai nhanh hơn ở những n bạn gặp thật.
| vẽ | bậc | tên gọi | hệ số nhân | hằng cộng | hàm chi phí |
|---|---|---|---|---|---|
| 1 | hằng số | 1 | |||
| log₂ n | lôgarit | log₂ n | |||
| n | tuyến tính | 100 × n | |||
| n log₂ n | tuyến tính nhân lôgarit | n log₂ n | |||
| n² | bình phương | n² | |||
| n³ | lập phương | n³ | |||
| 2ⁿ | hàm mũ | 2ⁿ | |||
| n! | giai thừa | n! |
2 · Điểm cắt: dưới mốc đó bậc cao hơn lại làm ít phép hơn ✎ sửa được
| n | A = 100 × n | B = n² | ai làm ít phép hơn |
|---|---|---|---|
| 99 | 9.900 | 9.801 | B ít hơn 99 phép |
| 100 | 10.000 | 10.000 | hoà, đúng bằng nhau |
| 101 | 10.100 | 10.201 | A ít hơn 101 phép |
n một và so hai vế: khi hai giá trị cách nhau xa thì so bằng số thực là đủ chắc, còn khi chúng sát nhau thì phép so được làm lại bằng số nguyên lớn, không làm tròn bước nào. Lần chạy này quét tới n = 200.000, trong đó 1 bước phải dùng tới số nguyên lớn. Mọi phép so đều cho kết luận chắc chắn.3 · Bảng giá trị ✎ sửa được
| hàm chi phí | n = 10 | n = 100 | n = 1.000 | n = 10.000 | n = 100.000 | n = 1.000.000 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| log₂ n | 3,32 | 6,64 | 9,97 | 13,29 | 16,61 | 19,93 |
| 100 × n | 1.000 | 10.000 | 100.000 | 1.000.000 | 10.000.000 | 100.000.000 |
| n log₂ n | 33,22 | 664,39 | 9.965,78 | 132.877,12 | 1,661 × 10^6 | 1,993 × 10^7 |
| n² | 100 | 10.000 | 1.000.000 | 100.000.000 | 10.000.000.000 | 1.000.000.000.000 |
| n³ | 1.000 | 1.000.000 | 1.000.000.000 | 1.000.000.000.000 | 1,000 × 10^15 | 1,000 × 10^18 |
| 2ⁿ | 1.024 | 1,268 × 10^30 | 1,072 × 10^301 | 1,995 × 10^3010⚠ tràn | 9,990 × 10^30102⚠ tràn | 9,901 × 10^301029⚠ tràn |
| n! | 3.628.800 | 9,333 × 10^157 | 4,024 × 10^2567⚠ tràn≈ ước lượng | 2,846 × 10^35659⚠ tràn≈ ước lượng | 2,824 × 10^456573⚠ tràn≈ ước lượng | 8,264 × 10^5565708⚠ tràn≈ ước lượng |
Infinity: nó dựng lại con số bằng số nguyên lớn rồi báo số chữ số. Ô có dấu ≈ ước lượng là ô mà n đã vượt luôn mức dựng số nguyên chính xác, chỉ còn công thức Stirling ước lượng lôgarit.4 · Đồ thị, hai trục đều là lôgarit ✎ sửa được
10^0.5 · Đổi số phép ra thời gian ✎ sửa được
| hàm chi phí | số phép ở n = 60 | thời gian ở 1.000.000.000 phép/giây | vượt tuổi vũ trụ từ n = |
|---|---|---|---|
| 1 | 1 | 1,0 ns | không, tới n = 1.000.000.000 vẫn kịp |
| log₂ n | 5,91 | 5,9 ns | không, tới n = 1.000.000.000 vẫn kịp |
| 100 × n | 6.000 | 6,0 µs | không, tới n = 1.000.000.000 vẫn kịp |
| n log₂ n | 354,41 | 354,4 ns | không, tới n = 1.000.000.000 vẫn kịp |
| n² | 3.600 | 3,6 µs | không, tới n = 1.000.000.000 vẫn kịp |
| n³ | 216.000 | 216,0 µs | 757.747.620 |
| 2ⁿ | 1,153 × 10^18 | 36,5 năm | 89 |
| n! | 8,321 × 10^81 | 1,912 × 10^55 lần tuổi vũ trụ⚠ vô vọng | 27 |
n nhỏ nhất mà thời gian chạy vượt qua nó, và nó phụ thuộc thẳng vào ô số phép mỗi giây bên trên: đổi tốc độ thì mốc đổi theo.6 · Chỗ số học của máy gãy ✎ sửa được
| n | số thực của máy in ra | giá trị đúng | tình trạng |
|---|---|---|---|
| 170 | 7,257 × 10^306 | 7,257 × 10^306 | còn giữ được |
| 171 | Infinity ⚠ tràn | 1,241 × 10^309 | 310 chữ số, dựng bằng số nguyên lớn |
- Nó đếm một phép tính tưởng tượng. Một phép ở đây không phải một lệnh máy: hai thuật toán cùng
O(n)có thể chênh nhau chục lần vì một cái đọc bộ nhớ liên tục còn cái kia nhảy lung tung. Chuyện đó không có mặt ở bất cứ đâu trong file này. - Nó không nói thuật toán nào nhanh hơn trên dữ liệu của bạn. Nó chỉ nói: với đúng hai hàm chi phí bạn vừa gõ vào, chỗ đổi vai nằm ở
nnào. - Số phép mỗi giây là con số bạn tự đặt, không phải kết quả đo trên máy nào. Nó chỉ đổi đơn vị từ phép sang giây.
- Tuổi vũ trụ là một phép đo đã công bố kèm sai số, chép vào đây ngày 29/07/2026. Cổng kiểm số canh phép chia, không canh vũ trụ học.
Hệ số là thứ O ném đi, còn máy thì không
Mở bài, sim đặt đường A là 100 × n và đường B là n². Theo nhãn O thì chuyện đã xong: O(n) thắng O(n²). Nhìn bảng ở mục 2 xem điều gì thật sự xảy ra.
Ở n = 99, đường A làm 9.900 phép còn đường B làm 9.801 phép. Tức là n² ít hơn 99 phép. Ở n = 100 hai bên bằng nhau đúng 10.000 phép. Phải sang tới n = 101 thì n² mới thật sự đắt hơn, 10.201 so với 10.100, tức nhiều hơn 101 phép. Xuống thấp nữa thì khoảng cách còn rõ hơn: ở n = 50, 100n mất 5.000 phép trong khi n² chỉ mất 2.500, đúng một nửa.
Chỗ này có một chi tiết nhỏ mà bỏ qua là sai cả bài: mốc hoà và mốc thua là hai số khác nhau. Ở đây là 100 và 101. Nếu bạn viết cổng kiểm hay viết điều kiện dừng bằng < trong khi phải là <=, lỗi sẽ nằm đúng ở khe một đơn vị đó và chạy đúng ở mọi chỗ khác. Sim in cả ba dòng 99, 100, 101 chính vì lý do này.
Điểm cắt trong sim không giải phương trình. Nó đi từng số nguyên n một và so hai vế. Khi hai giá trị cách nhau xa thì so bằng số thực là quá đủ chắc; khi chúng sát nhau thì phép so được làm lại bằng số nguyên lớn, không làm tròn bước nào. Ở cấu hình mở bài, cả lần quét chỉ có đúng một bước phải dùng tới số nguyên lớn, và bước đó chính là mốc hoà n = 100. Cách làm này quan trọng hơn nó có vẻ: giải 100n = n² trên giấy ra n = 100 chỉ được vì cặp đó dễ; đổi sang 1000 × n log₂ n + 1000 đấu với n² thì không còn giải tay được nữa, mà sim vẫn tìm ra mốc n = 13.747 và vẫn khẳng định được 13.746 còn nằm bên kia.
Đổi hệ số thì mốc đổi theo, và đổi theo cách đoán được. Đặt hệ số nhân của n thành a bất kỳ thì a × n gặp n² đúng tại n = a, vì a × a = a². Thêm một hằng cộng 5.000 vào đường A thì mốc đẩy từ 100 lên 137. Đây là lý do một thư viện được tối ưu kỹ với hệ số nhỏ có thể đánh bại một thuật toán bậc thấp hơn trên toàn bộ dải n mà bạn quan tâm.
Đổi số phép ra thời gian
Mục 5 chia số phép cho một tốc độ máy do bạn đặt. Mở bài là n = 60 và 1.000.000.000 phép mỗi giây. Bảng đọc như sau:
| hàm chi phí | số phép ở n = 60 | thời gian |
|---|---|---|
1 | 1 | 1,0 ns |
log₂ n | 5,91 | 5,9 ns |
100 × n | 6.000 | 6,0 µs |
n log₂ n | 354,41 | 354,4 ns |
n² | 3.600 | 3,6 µs |
n³ | 216.000 | 216,0 µs |
2ⁿ | 1,153 × 10^18 | 36,5 năm |
n! | 8,321 × 10^81 | 1,912 × 10^55 lần tuổi vũ trụ |
Bảng xếp theo bậc chứ không xếp theo giá, nên hai dòng 100 × n và n² là chỗ đáng soi: dòng bậc thấp hơn đứng trên, mà ở n = 60, tức là dưới mốc cắt 100, chính nó mới là dòng đắt hơn, 6,0 µs so với 3,6 µs. Cùng một câu chuyện với mục trước, chỉ đổi đơn vị.
Hai dòng cuối mới là chỗ đáng dừng lại. 2ⁿ với n = 60 ra hơn một tỉ tỉ phép, nghe rất khủng khiếp, nhưng chia cho một tỉ phép mỗi giây thì còn 36,5 năm. Dài tới mức vô dụng với một chương trình, nhưng nó không dài hơn tuổi vũ trụ, và bạn nên cảnh giác với những chỗ nói ngược lại. Muốn 2ⁿ thật sự vượt tuổi vũ trụ trên một máy tỉ phép mỗi giây thì phải lên tới n = 89: ở n = 88 còn kịp, n = 89 đã mất 1,42 lần tuổi vũ trụ. Sim tính ra mốc đó chứ không chép sẵn, nên bạn hạ tốc độ máy xuống một triệu phép mỗi giây thì mốc tự lùi về n = 79.
n! thì đi tới đó sớm hơn hẳn: mốc là n = 27. Ở n = 26 vẫn còn kịp, nhưng chỉ vừa đủ, khoảng 0,93 lần tuổi vũ trụ; sang n = 27 là 25,03 lần. Nếu bạn viết một hàm duyệt mọi hoán vị của 27 phần tử thì nó không chậm, nó là không bao giờ xong.
Đáng chú ý là ngay cả n³, một bậc đa thức trông hiền lành, cũng vượt tuổi vũ trụ khi n lên tới 757.747.620. Chỉ có điều n đó là gần tám trăm triệu, một con số bạn hầu như không gặp, nên trên thực tế n³ vẫn dùng được còn n! thì không. Ranh giới không nằm ở nhãn O, nó nằm ở chỗ dải n của bạn cắt vào đâu.
Chỗ số học của máy gãy
Số thực của máy dừng ở khoảng 1,798 × 10^308. Vượt qua đó thì phép nhân trả về Infinity, và đây không phải chuyện lý thuyết: nó xảy ra ngay trong cái bảng bạn vừa đọc.
n! còn giữ được tới n = 170, giá trị 7,257 × 10^306. Sang n = 171 là tràn. Sim không in Infinity: nó dựng lại 171! bằng số nguyên lớn rồi báo rằng con số đó có đúng 310 chữ số và bắt đầu bằng 1,241 × 10^309. 2ⁿ gãy muộn hơn, giữ được tới n = 1023 với 8,988 × 10^307, rồi tràn ở n = 1024.
Mốc tràn phụ thuộc vào hệ số, và đây là chỗ dễ quên nhất. Nếu hàm chi phí của bạn là 2 × 2ⁿ thì mốc lùi về n = 1023. Nếu là 100.000 × n! thì mốc lùi tận về n = 169. Bạn đổi ô hệ số nhân trong sim rồi nhìn mục 6 tính lại là thấy ngay.
Có một mức thứ hai nữa cần phân biệt. Tràn số thực là chuyện của kiểu dữ liệu; còn việc dựng được giá trị đúng thì tốn bộ nhớ và thời gian, nên sim chỉ dựng số nguyên chính xác cho n! tới n = 400 và cho 2ⁿ tới n = 4096. Quá mức đó thì nó bỏ giá trị đúng và chỉ giữ lại lôgarit, và hai bậc rơi vào hai cảnh khác nhau. Với n! thì lôgarit ấy là ước lượng thật, tính bằng công thức Stirling, và ô gọi đúng tên Stirling ra. Với 2ⁿ thì nó là n × log₁₀2, một đẳng thức chứ không phải ước lượng, tuy ô vẫn dùng chữ ước lượng cho gọn. Cái mất ở cả hai là phần đếm chữ số chính xác. Trong bảng mở bài, n! ở n = 1000 rơi vào đúng trường hợp này, còn 2ⁿ ở n = 1000 thì vẫn đủ chỗ: nó có 302 chữ số, vẫn nằm gọn trong số thực, và mốc tràn của nó phải tới n = 1024 mới đến.
Ba mức đó, tràn số thực, hết ngân sách số nguyên chính xác, và ước lượng, là ba trạng thái khác nhau. Một chương trình gộp chúng làm một sẽ in ra Infinity hoặc NaN rồi bạn mất luôn manh mối.
Bậc tăng nói được gì và không nói được gì
Trên đồ thị ở mục 4, hai trục đều là lôgarit. Mọi hàm đa thức khi đó là một đường thẳng và độ dốc chính là số mũ, nên chỗ hai đường thẳng giao nhau đúng là điểm cắt. Bốn bậc còn lại thì không phải đường thẳng: log₂ n và n log₂ n cong nhẹ, độ dốc của chúng tụt dần từ bậc 10 này sang bậc 10 kia chứ không đứng yên; còn 2ⁿ với n! thì dốc lên nhanh tới mức ra hẳn khỏi khung, với khung cao 12 bậc 10 thì n! ra khỏi khung ở n = 15 và 2ⁿ ra khỏi khung ở n = 40. Đó là hình ảnh trực quan nhất cho câu "hàm mũ và giai thừa không phải là một bậc đa thức cao".
Nhưng phải nói thẳng ranh giới của cả bài này. Bậc tăng không nói được thuật toán nào nhanh hơn trên dữ liệu thật của bạn. Nó nói ba chuyện, không hơn:
- Khi
nđủ lớn thì đường nào nằm dưới. "Đủ lớn" là bao nhiêu thì phải tính, và sim vừa cho bạn thấy nó có thể là 100, 137, hay 13.747. - Khi
ngấp đôi thì chi phí gấp mấy. Đây mới là chỗOthật sự hữu ích, vì câu trả lời không phụ thuộc hệ số. - Cái gì hoàn toàn không dùng được.
2ⁿvàn!thì không hệ số nào cứu nổi.
Còn "một phép tính" trong bài này là một phép tưởng tượng. Hai thuật toán cùng O(n) có thể chênh nhau chục lần vì một cái đọc bộ nhớ liên tục còn cái kia nhảy lung tung, và chuyện đó không có mặt ở bất cứ đâu trong sim. Số phép mỗi giây cũng là con số bạn tự đặt, không phải kết quả đo trên máy nào. Muốn biết cái nào nhanh hơn thật thì phải chạy và bấm giờ, chứ đếm bậc không thay được việc đó.
O giữ dáng đường và ném hệ số đi, nên nó chỉ trả lời được câu "khi n đủ lớn thì ai thắng", chứ không trả lời được câu "trên dữ liệu của tôi thì ai thắng". Với hệ số 100n đấu n², mốc đổi vai nằm ở n = 100, và dưới mốc đó thì n² làm ít phép hơn thật; mốc hoà 100 và mốc thua 101 là hai số khác nhau, nhầm là sai cả điều kiện dừng. Ở đầu kia của thang, 2ⁿ với n = 60 mất 36,5 năm ở một tỉ phép mỗi giây, còn n! chỉ cần n = 27 là đã vượt tuổi vũ trụ, và từ n = 171 thì chính số thực của máy cũng không giữ nổi con số nữa. Cả ba mốc đó đều tính ra được, nên đừng đoán.
- 1Thuật toán A tốn đúng 100n phép, thuật toán B tốn đúng n² phép. Dữ liệu của bạn luôn có n = 50. Chọn cái nào?
- 2Bạn tính n! trong một vòng lặp bằng kiểu số thực 64 bit. Từ n bằng bao nhiêu thì kết quả thành Infinity, và sim làm gì thay vì in ra chữ đó?
- 3Có người nói: "2ⁿ với n = 60 thì chạy lâu hơn tuổi vũ trụ". Sim cho biết gì?