Thiết kế và phân tích thuật toán: nghệ thuật giải bài toán cho nhanh
Vì sao chương trình này chạy một giây còn chương trình kia chạy cả thế kỷ: độ phức tạp, chia để trị, tham lam, quy hoạch động, đồ thị, bài toán khó.
Ban biên tập OpenER
Cập nhật 09/11/2026 · 14 phút đọc · CC BY 4.0
Bạn mở ứng dụng bản đồ, gõ điểm đến, và trong chưa tới một giây nó vẽ ra đường đi ngắn nhất qua hàng triệu đoạn đường của cả thành phố. Bạn gõ vài chữ vào ô tìm kiếm, và nó lục qua hàng tỷ trang web để đưa ra mười kết quả hợp nhất. Ứng dụng ngân hàng xác nhận giao dịch của bạn, trong khi cùng lúc đó kẻ gian không thể đoán ra khóa bảo mật dù có cả nghìn máy tính.
Đằng sau cả ba là cùng một thứ: thuật toán (algorithm) — một dãy bước rõ ràng để giải một bài toán. Và đằng sau sự khác biệt giữa "chưa tới một giây" với "chạy tới khi Mặt Trời tắt" thường không phải là máy nhanh hay chậm, mà là thuật toán được thiết kế khéo đến đâu, và người viết có biết phân tích nó trước khi chạy hay không.
Trước khi có phân tích thuật toán
Thuật toán già hơn máy tính rất nhiều. Khoảng năm 300 trước Công nguyên, Euclid đã mô tả cách tìm ước chung lớn nhất của hai số — một thuật toán ta vẫn dạy và vẫn dùng hôm nay. Bản thân chữ "algorithm" đến từ tên nhà toán học al-Khwarizmi ở Baghdad thế kỷ thứ IX, người viết sách về các phép tính từng bước với chữ số Ấn Độ – Ả Rập.
Thứ còn mới là phân tích thuật toán một cách có hệ thống. Ở những thập niên đầu của máy tính, cách đánh giá một chương trình rất thực dụng: chạy thử trên máy đang có, bấm giờ. Cách này có ba vấn đề:
- Kết quả gắn với một cái máy. Máy mới nhanh gấp đôi thì mọi con số cũ vô nghĩa. Hai người ở hai nơi không so được chương trình của nhau.
- Kết quả gắn với một bộ dữ liệu. Chạy tốt với 1.000 khách hàng không nói gì về 10 triệu khách hàng — và chính lúc có 10 triệu khách hàng là lúc chương trình chậm nhất phải trả giá.
- Chỉ biết sau khi đã viết xong. Không có cách nào nói trước "hướng này sẽ không bao giờ đủ nhanh, đừng tốn công".
Ngành học hình thành từng bước:
- Đếm bước thay vì đếm giây — thập niên 1960. Các nhà nghiên cứu như Juris Hartmanis và Richard Stearns (1965) đặt nền cho việc đo độ khó của bài toán bằng số bước theo kích thước dữ liệu vào, không phụ thuộc máy.
- Phân tích thành một môn chính thức. Donald Knuth bắt đầu bộ sách The Art of Computer Programming (tập đầu năm 1968), phân tích tỉ mỉ từng thuật toán, và phổ biến cách dùng ký hiệu O lớn — mượn từ lý thuyết số — trong khoa học máy tính.
- Bài toán "khó" có tên — năm 1971–1972, Stephen Cook rồi Richard Karp chỉ ra rằng rất nhiều bài toán thực tế — xếp lịch, đóng thùng, tìm đường qua mọi thành phố — cùng chung một mức khó, gọi là NP-đầy đủ (NP-complete). Từ đó người ta biết khi nào nên ngừng tìm lời giải hoàn hảo.
Đặt cạnh nhau:
Không phân tích | Có phân tích | |
|---|---|---|
Biết chương trình nhanh hay chậm | Sau khi viết xong và chạy thử | Trước khi viết, từ ý tưởng |
Khi dữ liệu tăng gấp 1.000 lần | Không biết — thường là bất ngờ khó chịu | Dự đoán được: chậm gấp 1.000, gấp 1 triệu, hay chậm hơn nhiều |
So hai cách giải | Phụ thuộc máy, dữ liệu, người chạy | So được trên giấy, ở đâu cũng như nhau |
Gặp bài toán khó | Thử mãi không ra, không biết vì sao | Nhận ra nó khó, chuyển sang lời giải gần đúng |
Muốn nhanh hơn | Mua máy mạnh hơn | Đổi thuật toán — thường lợi hơn nhiều lần |
"Không phân tích" vẫn còn rất phổ biến hôm nay. Một trang web chạy mượt lúc thử với vài chục bản ghi, rồi treo cứng khi có vài trăm nghìn người dùng, vì ai đó lồng hai vòng lặp qua cùng một danh sách. Một bảng tính Excel mất cả phút để tính lại vì mỗi ô tra cứu cả bảng. Phần lớn những lần "phải nâng cấp máy chủ" thật ra là một thuật toán có thể sửa trong một buổi chiều.
Môn này trả lời câu hỏi gì
Môn Thiết kế và phân tích thuật toán trả lời hai câu hỏi đi cùng nhau:
- Thiết kế: với một bài toán, làm sao nghĩ ra cách giải đúng và hiệu quả? Có những "khuôn" nào lặp đi lặp lại mà ta học được?
- Phân tích: làm sao chứng minh cách giải đó luôn đúng, và ước lượng nó tốn bao nhiêu thời gian, bao nhiêu bộ nhớ khi dữ liệu lớn dần — trước khi chạy?
Và một câu hỏi thứ ba, khiêm tốn hơn: khi nào một bài toán khó tới mức không ai biết cách giải nhanh, và khi đó nên làm gì?
Vì sao cần học? Vì máy tính nhanh lên mỗi năm, nhưng dữ liệu lớn lên còn nhanh hơn. Một thuật toán tốt trên máy cũ thường thắng một thuật toán tồi trên siêu máy tính. Và vì đây là ngôn ngữ chung của nghề: phỏng vấn kỹ thuật ở các công ty công nghệ, các kỳ thi lập trình, các bài báo nghiên cứu — đều nói bằng ngôn ngữ của môn này.
Năm ý tưởng cốt lõi
1. Đo bằng tốc độ tăng, không bằng giây
Thay vì hỏi "chạy mất bao nhiêu giây", ta hỏi: khi dữ liệu có n phần tử, thuật toán cần khoảng bao nhiêu bước, và con số đó tăng thế nào khi n tăng? Ta bỏ qua hằng số và các phần nhỏ, chỉ giữ phần tăng nhanh nhất, viết bằng ký hiệu O lớn (Big-O).
Bảng dưới đây cho thấy vì sao phần tăng nhanh nhất là thứ duy nhất đáng bận tâm. Giả sử máy làm được một tỷ bước mỗi giây:
Số bước | n = 1.000 | n = 1 triệu | n = 1 tỷ |
|---|---|---|---|
log n | tức thì | tức thì | tức thì |
n | tức thì | khoảng 1 phần nghìn giây | khoảng 1 giây |
n log n | tức thì | khoảng 20 phần nghìn giây | khoảng 30 giây |
n² | khoảng 1 phần nghìn giây | khoảng 17 phút | khoảng 30 năm |
2ⁿ | lâu hơn tuổi vũ trụ | — | — |
Từ n sang n² là khác biệt giữa "một giây" và "ba mươi năm". Không có chiếc máy nào bù được khoảng cách đó. Đây là lý do người học thuật toán nhìn một vòng lặp lồng trong vòng lặp là thấy ngay rủi ro.
2. Chia để trị
Tìm một cái tên trong danh bạ một triệu người. Cách ngây thơ: đọc từng dòng — tới một triệu bước. Cách khôn: mở giữa cuốn, xem tên cần tìm đứng trước hay sau, bỏ hẳn một nửa, lặp lại. Mỗi bước chia đôi, nên chỉ khoảng 20 bước là xong, vì 2²⁰ đã hơn một triệu. Đó là tìm kiếm nhị phân (binary search):
def tim_nhi_phan(ds, x):
"""ds đã sắp xếp tăng dần; trả về vị trí của x, hoặc -1 nếu không có."""
trai, phai = 0, len(ds) - 1
while trai <= phai:
giua = (trai + phai) // 2
if ds[giua] == x:
return giua
if ds[giua] < x:
trai = giua + 1 # x nằm ở nửa phải, bỏ nửa trái
else:
phai = giua - 1 # x nằm ở nửa trái, bỏ nửa phải
return -1Đây là một trường hợp của khuôn chia để trị (divide and conquer): chia bài toán thành bài toán nhỏ hơn cùng dạng, giải từng phần, rồi ghép lại. Sắp xếp trộn (merge sort) dùng cùng ý tưởng — chia đôi danh sách, sắp từng nửa, trộn hai nửa đã sắp — và sắp được một triệu phần tử trong khoảng 20 triệu bước, thay vì một nghìn tỷ bước của cách so từng cặp. Môn học dạy cách viết thời gian chạy của những thuật toán này thành công thức truy hồi (recurrence) rồi giải nó, để biết chắc thay vì đoán.
3. Tham lam hay quy hoạch động
Bạn cần trả lại 6 đồng tiền thừa bằng ít đồng xu nhất. Cách tự nhiên là tham lam (greedy): mỗi lần lấy đồng lớn nhất còn vừa. Với tiền Việt Nam (1.000, 2.000, 5.000, 10.000…) cách này luôn cho kết quả tốt nhất. Nhưng thử một hệ tiền xu chỉ có mệnh giá 1, 3 và 4:
- Tham lam: lấy 4, còn 2, lấy 1, lấy 1 — 3 đồng.
- Tốt nhất: 3 + 3 — 2 đồng.
Tham lam nhanh và thường đúng, nhưng không phải lúc nào cũng đúng — và phần quan trọng của môn học là chứng minh khi nào nó đúng.
Khi tham lam sai, ta dùng quy hoạch động (dynamic programming): giải mọi bài toán con một lần, ghi lại kết quả, rồi xây đáp án lớn từ các đáp án nhỏ. Với bài đổi tiền, "ít đồng nhất để trả số tiền a" bằng một cộng với giá trị tốt nhất của "ít đồng nhất để trả a trừ một mệnh giá nào đó":
def it_dong_nhat(menh_gia, so_tien):
VO_CUC = float("inf")
tot_nhat = [0] + [VO_CUC] * so_tien # tot_nhat[a]: số đồng ít nhất để trả a
for a in range(1, so_tien + 1):
for m in menh_gia:
if m <= a and tot_nhat[a - m] + 1 < tot_nhat[a]:
tot_nhat[a] = tot_nhat[a - m] + 1
return tot_nhat[so_tien]
print(it_dong_nhat([1, 3, 4], 6)) # 2Cái tên "quy hoạch động" do Richard Bellman đặt trong thập niên 1950, và chính ông kể rằng chọn tên một phần vì nó nghe ấn tượng. Ý tưởng thì có ở khắp nơi: so khớp hai chuỗi ADN, tính độ khác nhau giữa hai đoạn văn bản, chọn hàng cho vào thùng xe sao cho có lời nhất.
4. Đồ thị: mô hình của gần như mọi thứ
Rất nhiều bài toán thực tế hóa ra là cùng một thứ: đồ thị (graph) — một tập điểm nối với nhau bằng cạnh. Bản đồ là đồ thị (ngã tư và đoạn đường). Mạng xã hội là đồ thị (người và quan hệ bạn bè). Internet là đồ thị (router và đường truyền). Các môn học trong một lộ trình là đồ thị (môn và quan hệ "phải học trước").
Học xong vài thuật toán đồ thị, bạn giải được cả một họ bài toán:
- Đường đi ngắn nhất: thuật toán của Edsger Dijkstra (công bố năm 1959) tìm đường ngắn nhất từ một điểm tới mọi điểm khác — nền của các ứng dụng chỉ đường. Dijkstra kể ông nghĩ ra nó trong khoảng hai mươi phút, ngồi ở một quán cà phê ở Amsterdam, không cần giấy bút.
- Duyệt đồ thị theo chiều rộng hay chiều sâu: tìm "bạn của bạn", kiểm tra hai điểm có nối được với nhau không.
- Sắp xếp tô-pô (topological sort): xếp các việc có ràng buộc trước – sau, ví dụ thứ tự học các môn hay thứ tự biên dịch các file.
- Cây khung nhỏ nhất: nối mọi điểm với tổng chi phí ít nhất — đặt cáp, đặt ống nước.
5. Khi bài toán thật sự khó
Có những bài toán mà không ai biết thuật toán nhanh để giải. Ví dụ quen thuộc: một người giao hàng phải đi qua 30 điểm rồi quay về, tìm thứ tự đi ngắn nhất. Thử hết mọi thứ tự thì có khoảng 10³⁰ cách — không máy nào thử xong.
Bài toán này thuộc nhóm NP-đầy đủ. Cả nhóm có một tính chất lạ: nếu ai tìm ra thuật toán nhanh cho một bài, thì tất cả các bài trong nhóm đều giải nhanh được. Câu hỏi "có tồn tại thuật toán nhanh như vậy hay không" — P có bằng NP không — là một trong bảy Bài toán Thiên niên kỷ của Viện Toán học Clay, treo thưởng một triệu đô la, và vẫn chưa có lời giải.
Biết một bài toán thuộc nhóm này là kiến thức rất thực dụng: bạn thôi tìm lời giải hoàn hảo, và chuyển sang thuật toán xấp xỉ (chứng minh được kết quả không tệ hơn tối ưu quá bao nhiêu), heuristic (thường tốt trong thực tế), hoặc giới hạn bài toán lại cho vừa sức. Và điều ngược lại cũng quan trọng: mật mã hiện đại dựa vào việc có những bài toán khó — nếu ngày mai ai đó giải nhanh được chúng, phần lớn bảo mật trên Internet phải làm lại.
Thuật toán nằm ở đâu trong chồng tầng
Nếu bạn đã đọc Từ electron đến ứng dụng, máy tính là một chồng tầng trừu tượng, từ electron lên tới ứng dụng. Thuật toán đứng hơi khác: nó không nằm ở một tầng nào, mà là cách suy nghĩ dùng ở mọi tầng.
- Ở tầng thấp: phần cứng dùng thuật toán để cộng, nhân, chia số; bộ nhớ đệm dùng thuật toán để quyết định giữ gì, bỏ gì.
- Ở giữa: hệ điều hành dùng thuật toán lập lịch và quản lý bộ nhớ; mạng máy tính dùng thuật toán định tuyến và kiểm soát tắc nghẽn.
- Ở trên: cơ sở dữ liệu chọn cách chạy truy vấn, công cụ tìm kiếm xếp hạng trang, mô hình học máy được huấn luyện bằng thuật toán tối ưu.
Phân tích thuật toán dùng một mô hình máy trừu tượng — đếm bước, không đếm giây — chính là để kết quả đúng bất kể chồng tầng bên dưới là gì.
Học trước và học sau
· 7 mônCấu trúc dữ liệu và giải thuật
Data Structures and Algorithms
Học trước sẽ dễ hơn: mảng, danh sách, cây, bảng băm, các thuật toán cơ bản.
Toán rời rạc, logic và chứng minh
Mathematics for Computer Science
Học trước sẽ dễ hơn: quy nạp, chứng minh, tổ hợp, xác suất.
Lý thuyết tính toán
Theory of Computation
Học sau: giới hạn của máy tính.
Kinh tế học thuật toán
Algorithmic Economics
Học sau, dùng lại môn này.
Thuật toán cho sinh học tính toán
Algorithms for Computational Biology
Học sau, dùng lại môn này.
Xem chủ đề trên OpenER: Algorithms for Computational Biology
Ứng dụng thật và nghề nghiệp
- Phỏng vấn kỹ thuật: phần lớn công ty công nghệ lớn trong và ngoài nước phỏng vấn kỹ sư phần mềm bằng bài toán thuật toán. Đây là môn có lợi ích trực tiếp nhất cho việc tìm việc.
- Lập trình thi đấu: Olympic Tin học, ICPC — nơi nhiều kỹ sư giỏi bắt đầu, và là cách luyện môn này nhanh nhất.
- Backend và hệ thống lớn: chọn đúng cấu trúc dữ liệu và thuật toán là khác biệt giữa hệ thống chịu được triệu người dùng và hệ thống sập.
- Bản đồ, logistics, giao hàng: tìm đường, xếp lịch xe, xếp hàng vào kho.
- Dữ liệu và AI: huấn luyện mô hình là bài toán tối ưu; xử lý dữ liệu lớn cần thuật toán chạy được trên hàng tỷ dòng.
- Tài chính định lượng, sinh học tính toán, nghiên cứu.
Học xong làm được gì, bắt đầu từ đâu
Sau môn này bạn có thể:
- nhìn một đoạn code và ước lượng nó chạy được với bao nhiêu dữ liệu;
- nhận ra một bài toán mới thuộc khuôn nào — chia để trị, tham lam, quy hoạch động, đồ thị — và bắt đầu từ đó;
- chứng minh thuật toán của mình đúng, không chỉ "chạy thử thấy đúng";
- nhận ra bài toán khó để khỏi phí công tìm lời giải hoàn hảo;
- tự tin ở vòng phỏng vấn thuật toán.
Nên biết trước: lập trình thành thạo một ngôn ngữ, các cấu trúc dữ liệu cơ bản, và quen với chứng minh quy nạp. Chưa vững thì đi qua các chủ đề Data Structures and Algorithms và Mathematics for Computer Science trước.
Bắt đầu trên OpenER: trang chủ đề Design and Analysis of Algorithms có các khóa học đã chọn lọc, và hướng dẫn học gợi ý thứ tự đi qua chúng. Lời khuyên chung của người dạy môn này: đừng chỉ xem bài giảng. Thuật toán chỉ vào đầu khi bạn tự giải bài — mỗi tuần vài bài, tự chứng minh, tự cài đặt, rồi mới xem lời giải.
Tài liệu tham khảo
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein — Introduction to Algorithms (thường gọi CLRS).
- Jon Kleinberg, Éva Tardos — Algorithm Design.
- Jeff Erickson — Algorithms, đọc miễn phí tại trang của tác giả (Đại học Illinois).
- Tim Roughgarden — bộ sách Algorithms Illuminated và các khóa giảng ở Stanford.
- MIT 6.046J Design and Analysis of Algorithms — bài giảng mở trên MIT OpenCourseWare.