Những Gì Khóa Học Đã Dạy & Những Gì Bị Bỏ Qua
Khóa học của Hamming bao gồm: chuyển đổi tương tự-số, sửa lỗi, mô phỏng, thống kê, phân tích số và hình học n-chiều. Ông tư duy theo hướng tính toán — xử lý tín hiệu, lý thuyết mã hóa, lọc số đều đòi hỏi tư duy tính toán.
Ông chưa bao giờ dạy một cách có hệ thống về độ phức tạp thuật toán.
Tại Sao Khoảng Trống Tồn Tại
Mô hình tư duy của Hamming được hình thành trong thời đại mà các nút thắt phần cứng chiếm ưu thế. Câu hỏi: bao nhiêu transistor trên mỗi chip? Thuật toán chạy trên phần cứng hiện có. Ở N=100, thuật toán O(N²) tốn 10.000 phép tính. Ở N=1.000, nó tốn 1.000.000. Ở N=10.000 (thông thường ngày nay trong đồ thị phụ thuộc, mạng xã hội, & trình quản lý gói): nó tốn 100.000.000. Sự khác biệt giữa O(N) & O(N²) không thể thấy được ở quy mô Hamming làm việc, & thảm khốc ở quy mô mà học trò ông sẽ sống.
Donald Knuth xuất bản The Art of Computer Programming bắt đầu từ năm 1968 — cùng năm Hamming đang ở đỉnh cao năng suất nghiên cứu. Ký hiệu Big O trở thành ngôn ngữ thuật toán chuẩn vào những năm 1970 & 1980. Khóa học của Hamming diễn ra năm 1995, nhưng mô hình tư duy về tính toán của ông được hình thành sớm hơn. Ông chưa bao giờ cập nhật chương này.
Một điều cơ bản theo tiêu chí của chính Hamming
Tiêu chí của Hamming cho một điều cơ bản: (1) nó đã tồn tại lâu dài, (2) phần còn lại của lĩnh vực có thể được suy ra từ nó bằng các phương pháp chuẩn.
Big O vượt qua cả hai tiêu chí. Phân tích tốc độ tăng trưởng đã tồn tại từ thời Knuth. Từ đó, bạn suy ra việc chọn thuật toán, lựa chọn cấu trúc dữ liệu, & dự đoán hiệu năng — hầu hết khoa học máy tính thực hành đều xuất phát từ việc hỏi “chi phí tăng như thế nào khi N tăng?” Hamming đã bỏ lỡ điều cơ bản bền vững nhất của chính lĩnh vực mình.
Big O như một điều cơ bản
Hamming dạy rằng những điều cơ bản tồn tại lâu hơn các công nghệ cụ thể. Ông lấy giải tích làm ví dụ: được phát minh một lần, áp dụng được cho vật lý, kỹ thuật, kinh tế, & sinh học trong nhiều thế kỷ. Các công cụ ngoại vi đến rồi đi; những điều cơ bản tích lũy.
Cách chi phí tăng trưởng
Big O đo lường cách chi phí tăng trưởng khi đầu vào tăng. Không phải hệ số hằng số — mà là tốc độ. Hai thuật toán cùng chạy trong 'vài mili giây' ở N=100 có thể chênh lệch nhau tới 10.000 lần ở N=10.000, nếu một cái chạy trong O(N) và cái kia trong O(N²).
Các lớp độ phức tạp phổ biến
O(1) — Hằng số. Chi phí như nhau bất kể N. Ví dụ: tra cứu bảng băm theo khóa, truy cập mảng theo chỉ số, push/pop ngăn xếp. Nhân đôi N không thay đổi gì.
O(log N) — Logarit. Mỗi bước giảm một nửa công việc còn lại. Ví dụ: tìm kiếm nhị phân trong mảng đã sắp xếp, truy vấn không gian BVH trong game engine, các thao tác trên cây nhị phân cân bằng. Với N=1.000.000: log₂(1.000.000) ≈ 20 bước.
O(N) — Tuyến tính. Chi phí tăng theo kích thước đầu vào. Ví dụ: quét tuyến tính danh sách, đọc file, đếm số phần tử trong tập hợp. Với N=10.000: 10.000 phép toán.
O(N log N) — Tuyến tính-logarit. Gần như tuyến tính, nhưng hơi tệ hơn một chút. Ví dụ: sắp xếp trộn (merge sort), thuật toán đường đi ngắn nhất hiệu quả (Dijkstra với heap). Với N=10.000: ~133.000 phép toán.
O(N²) — Bậc hai. Chi phí tăng mạnh. Ví dụ: gọi list.contains() bên trong vòng lặp trên cùng danh sách, sắp xếp nổi bọt (bubble sort), so sánh tất cả các cặp theo cách ngây thơ. Với N=1.000: 1.000.000 phép toán. Với N=10.000: 100.000.000 phép toán.
O(2^N) — Hàm mũ. Không thể sử dụng ở bất kỳ quy mô có ý nghĩa nào. Ví dụ: tổ hợp vét cạn, tìm tất cả tập con. Với N=30: hơn 1.000.000.000 phép tính.
Quy mô khiến điều này trở nên rõ ràng
N=10 phép so sánh:
O(N): 10
O(N²): 100
tỷ lệ: 10x
N=1.000 so sánh:
O(N): 1.000
O(N²): 1.000.000
tỷ lệ: 1.000x
N=10.000 so sánh:
O(N): 10,000
O(N²): 100,000,000
ratio: 10,000xKhi N=10, sự khác biệt gần như không đáng kể. Khi N=10.000, thuật toán O(N²) chạy chậm hơn 10.000 lần. Đây là lý do MOAD-0001 gần như không bị phát hiện trong nhiều thập kỷ: các đồ thị mà nó chạy vào năm 1993 chỉ có 50 nút. Đến năm 2020, cùng đoạn mã đó chạy trên các đồ thị phụ thuộc với 50.000 nút.
Phân loại Ba Thao tác
Áp dụng các lớp độ phức tạp cho các thao tác cụ thể. Câu hỏi then chốt cho mỗi thao tác: cần bao nhiêu phép tính khi N tăng?
Mã đúng, nhưng đường cong tăng trưởng sai
Mã đúng chạy trong thời gian O(N²) cho kết quả giống hệt mã O(N). Các bài kiểm tra đều vượt qua. Kết quả đầu ra khớp. Không có ngoại lệ nào xảy ra. Lỗi nằm ẩn trong đường cong tăng trưởng.
Tính chất này khiến các lỗi O(N²) trở nên trầm tích: chúng hóa đá bên trong mã đang hoạt động và chỉ lộ diện khi N vượt qua một ngưỡng nhất định. Mã không thay đổi. Thế giới xung quanh nó đã thay đổi.
MOAD-0001: Lỗi trầm tích
Trường hợp phổ biến nhất: visited = [] bên trong vòng lặp duyệt đồ thị.
visited = []
for node in graph:
if node not in visited: # quét O(N) mỗi lần gọi
visited.append(node)
process(node)Mỗi lần gọi not in visited phải quét từ 0 đến len(visited)-1 phần tử. N lần gọi × trung bình N/2 phần tử được quét = tổng độ phức tạp O(N²). Cách khắc phục: chỉ một dòng.
visited = set() # Kiểm tra thành viên O(1)
for node in graph:
if node not in visited: # Tra cứu băm O(1)
visited.add(node)
process(node)Hành vi giống nhau. Kết quả giống nhau. Các bài kiểm tra vẫn vượt qua. Tốc độ tăng trưởng thay đổi từ O(N²) sang O(N). Tại N=1.000: nhanh hơn 1.000×. Tại N=10.000: nhanh hơn 10.000×.
Tại sao thời đại của Hamming đã gieo mầm cho điều này
Trong Java & C ban đầu, ArrayList (mảng động) là container tuần tự mặc định. Set tồn tại nhưng không phải là cách dùng phổ biến — nhà phát triển thường chọn thứ quen thuộc. Một thuật toán duyệt đồ thị năm 1993 với N=50 chạy ở mức micro giây khi dùng visited = []. Đoạn mã đó được đưa vào version control, được sao chép, được đóng gói trong thư viện, được phát hành qua package manager. Đến năm 2020, cùng mẫu đó chạy trên đồ thị phụ thuộc với 50.000 nút.
Mã nguồn đúng vào năm 1993. Nó trở nên tốn kém khi thế giới xung quanh thay đổi. Thời đại của Hamming đã gieo mầm cho loại lỗi này vì chưa bao giờ đặt câu hỏi về tốc độ tăng trưởng.
Chẩn đoán & Sửa
Áp dụng chẩn đoán: tìm mẫu O(N²), xác định cách sửa.
Những thay đổi về đặt tên
Trước khi Big O có tên, lập trình viên chỉ nhận thấy “chương trình này chạy chậm”. Họ profile, họ viết lại. Nhưng họ không thể dạy được mô hình — họ chỉ có thể chỉ ra từng trường hợp cụ thể. Một mô hình không có tên thì không thể lan truyền.
Sau khi Big O có tên, một kỹ sư cao cấp có thể nói “đây là O(N²), hãy thay bằng set” và kỹ sư junior có thể hiểu, áp dụng, rồi dạy lại mô hình đó. Tên gọi đã biến mô hình thành một đơn vị tri thức có thể truyền đạt.
Hamming đã nhận ra động lực này ở các lĩnh vực khác. Ông mô tả việc đặt tên “spaghetti code” những năm 1960 đã giúp cộng đồng nhận diện, thảo luận và cuối cùng loại bỏ một loại lỗi mà ai cũng từng gặp nhưng chưa ai đặt tên. Cơ chế tương tự cũng áp dụng cho các lớp độ phức tạp.
Unhamming bổ sung vốn từ vựng mà Hamming chưa nhắc đến: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). Những tên gọi này giúp bạn nhìn thấy đường cong tăng trưởng ngay trong mã nguồn, dự đoán hiệu năng khi mở rộng, và truyền đạt cách sửa một cách chính xác. Chúng đáp ứng tiêu chí của Hamming về một khái niệm nền tảng: bền vững và sinh ra hầu hết các phần còn lại của lĩnh vực. [TITLE who_coined_big_o/]
Từ Lý Thuyết Số đến Khoa Học Máy Tính
Ký hiệu Big O không bắt nguồn từ khoa học máy tính. Nó xuất phát từ toán học thuần túy — cụ thể là lý thuyết số — 74 năm trước khi Donald Knuth áp dụng nó cho thuật toán.
Paul Bachmann, 1894
Paul Bachmann, nhà toán học người Đức, đã giới thiệu ký hiệu O trong cuốn sách năm 1894 Die Analytische Zahlentheorie (Lý Thuyết Số Giải Tích). Ông cần một cách ngắn gọn để diễn tả rằng một đại lượng không tăng nhanh hơn đại lượng khác, với một hằng số nhân. Viết 'f(n) = O(g(n))' có nghĩa: f tăng không nhanh hơn g. Điều này giúp các nhà lý thuyết số lập luận về các sai số trong các phép xấp xỉ mà không cần theo dõi các hằng số chính xác.
Bachmann không nghĩ về vòng lặp, cấu trúc dữ liệu hay thời gian thực thi. Ông đang nghĩ về cách các số nguyên tố phân bố — cụ thể là về các sai số trong Định Lý Số Nguyên Tố.
Edmund Landau, 1909
Edmund Landau, một nhà toán học người Đức khác, đã phổ biến ký hiệu này trong cuốn Handbuch der Lehre von der Verteilung der Primzahlen (Sổ Tay về Phân Bố Số Nguyên Tố) năm 1909. Landau cũng giới thiệu ký hiệu liên quan o (little-o) và sử dụng họ các ký hiệu tiệm cận rộng rãi đến mức họ này được gọi là Ký hiệu Bachmann-Landau hoặc đơn giản là Ký hiệu Landau.
Trong sáu thập kỷ, ký hiệu O hoàn toàn tồn tại trong toán học. Không có lập trình viên nào nghĩ về nó.
Donald Knuth, 1968 & 1976
Donald Knuth đã chuyển đổi ký hiệu này sang khoa học máy tính. Trong The Art of Computer Programming (Tập 1, 1968), Knuth sử dụng ký hiệu O để mô tả thời gian chạy của thuật toán — một sự chuyển giao trực tiếp công cụ của Bachmann sang một lĩnh vực mới. Ông là người đầu tiên áp dụng nó một cách có hệ thống vào phân tích thuật toán.
Năm 1976, Knuth xuất bản một bài báo ngắn trên SIGACT News với tiêu đề 'Big Omicron and Big Omega and Big Theta.' Ông giới thiệu Omega (Ω) cho cận dưới và Theta (Θ) cho cận chặt, hoàn thiện bộ ba ký hiệu mà khoa học máy tính sử dụng ngày nay. Ông cũng lập luận về việc chuẩn hóa việc sử dụng các ký hiệu này trên toàn lĩnh vực — một hành động chuẩn hóa có chủ đích đã thúc đẩy sự chấp nhận rộng rãi.
Đến đầu những năm 1980, Big O xuất hiện trong mọi giáo trình thuật toán. Đến những năm 1990, nó trở thành từ vựng chuẩn trong phỏng vấn.
Hành trình 74 năm
1894 — Bachmann giới thiệu O trong lý thuyết số
1909 — Landau phổ biến O, o và toàn bộ họ ký hiệu
1953 — Hamming bắt đầu nghiên cứu tại Bell Labs (không bao giờ học Big O như công cụ CS)
1968 — Knuth áp dụng O vào phân tích thuật toán trong TAOCP Vol. 1
1976 — Knuth thêm Omega và Theta; lập luận cho việc chuẩn hóa
1980s — Big O trở thành một phần của tất cả chương trình giảng dạy CS
1993 — Lớp trầm tích MOAD-0001 hình thành trong mã production
1995 — Hamming dạy phiên bản cuối cùng của khóa học; không bao giờ đề cập Big O
2026 — MOAD-0001 được tìm thấy trong hơn 1.000 dự án mã nguồn mởCông cụ của Bachmann đã tồn tại 74 năm trong lĩnh vực toán học thuần túy, hiển nhiên với mọi nhà toán học nhưng vô hình với mọi lập trình viên. Knuth đã nhìn ra và thực hiện sự chuyển đổi. Hamming — cùng thời đại, cùng cộng đồng máy tính — chưa bao giờ đưa nó vào khóa học của mình.
Tại sao việc chuẩn hóa của Knuth lại quan trọng
Bài báo năm 1976 của Knuth không chỉ giới thiệu Omega và Theta. Ông lập luận rằng lĩnh vực này cần một ký hiệu thống nhất, và ký hiệu không nhất quán đang gây hại thực sự. Các giáo trình khác nhau dùng O với ý nghĩa khác nhau — đôi khi là cận trên, đôi khi là xấp xỉ, đôi khi không rõ hằng số có quan trọng hay không. Knuth đã làm rõ tất cả.
Đây chính là động lực đặt tên mẫu hình của Hamming được áp dụng cho chính ký hiệu. Trước khi Knuth chuẩn hóa các ký hiệu, các kỹ sư không thể truyền đạt các tuyên bố về độ phức tạp một cách chính xác giữa các giáo trình, bài báo hay đội nhóm. Sau khi chuẩn hóa, “chạy trong O(N log N)” chỉ mang đúng một ý nghĩa, bất kể ai nói.
Knuth cũng đưa ra cách diễn giải phi chính thức: “O(f(n)) nghĩa là thời gian chạy nhiều nhất là một hằng số nhân với f(n), với mọi n đủ lớn.” Cách hiểu này — cận trên, nhân với hằng số, cho dữ liệu lớn — trở thành trực giác chuẩn mà mọi lập trình viên đều học.