Thuật toán là gì? Đây là câu hỏi đầu tiên của hầu hết người mới bắt đầu học lập trình. Hiểu đơn giản, thuật toán là một chuỗi các bước xác định, có thứ tự, dùng để giải quyết một bài toán cụ thể. Khi bạn sắp xếp danh bạ theo tên, tìm đường trên Google Maps hay gợi ý video trên YouTube, một thuật toán đang âm thầm chạy phía sau. Bài viết này sẽ giải thích thuật toán từ con số không, kèm các ví dụ dễ hiểu nhất.
Thuật toán là gì?
Một thuật toán phải thỏa mãn bốn đặc tính cơ bản: xác định (mỗi bước rõ ràng, không mơ hồ), hữu hạn (kết thúc sau số bước nhất định), đầu vào và đầu ra rõ ràng, và hiệu quả (thực thi được). Ví dụ kinh điển nhất: thuật toán nấu mì gói — đun nước, cho mì vào, thêm gia vị, đợi ba phút. Nếu thiếu một bước, kết quả sẽ sai. Lập trình cũng vậy: máy tính chỉ làm đúng những gì thuật toán mô tả.
Trong lập trình, bạn không chỉ cần thuật toán đúng mà còn cần thuật toán nhanh. Một chương trình tìm kiếm chạy trong một giây hay mười phút khác biệt hoàn toàn trải nghiệm người dùng. Đây là lúc khái niệm độ phức tạp thuật toán xuất hiện.
Độ phức tạp Big-O là gì?
Big-O là cách đo lượng thao tác mà thuật toán thực hiện khi kích thước dữ liệu tăng lên, ký hiệu bằng O(…). Bạn không cần nhớ công thức toán học phức tạp, chỉ cần nắm bốn mức phổ biến:
| Ký hiệu | Ý nghĩa | Ví dụ |
|---|---|---|
| O(1) | Thời gian không đổi, luôn chạy nhanh | Lấy phần tử theo chỉ số trong mảng |
| O(log n) | Tăng rất chậm, cực kỳ hiệu quả | Tìm kiếm nhị phân |
| O(n) | Tăng tuyến tính theo dữ liệu | Duyệt danh sách một lần |
| O(n log n) | Hiệu quả cho bài toán sắp xếp | Sắp xếp nhanh Quicksort |
| O(n²) | Tăng nhanh, chỉ dùng khi dữ liệu nhỏ | Sắp xếp nổi bọt |
Ý tưởng cốt lõi: với cùng một bài toán, chọn thuật toán có Big-O nhỏ hơn sẽ giúp chương trình xử lý dữ liệu lớn mà không bị nghẽn.
Thuật toán tìm kiếm
Tìm kiếm tuyến tính
Cách tự nhiên nhất: duyệt từ đầu đến cuối danh sách, so sánh từng phần tử với giá trị cần tìm. Đơn giản, dễ viết, nhưng với danh sách 1 triệu phần tử bạn có thể phải duyệt cả 1 triệu lần, độ phức tạp O(n).
Tìm kiếm nhị phân
Nếu danh sách đã sắp xếp, bạn dùng tìm kiếm nhị phân: so sánh giá trị cần tìm với phần tử giữa, nếu nhỏ hơn thì chỉ xét nửa trái, lớn hơn thì xét nửa phải, lặp lại. Mỗi bước loại bỏ một nửa dữ liệu, nên với 1 triệu phần tử chỉ cần khoảng 20 bước, độ phức tạp O(log n). Vì thế danh bạ điện thoại luôn được sắp xếp theo tên — để bạn tìm được ai đó chỉ trong vài giây.
Thuật toán sắp xếp
Sắp xếp nổi bọt
So sánh hai phần tử liền kề và hoán đổi nếu sai thứ tự, lặp lại nhiều vòng. Dễ hiểu, dễ cài nhưng chạy O(n²): với 10.000 phần tử cần tới 100 triệu thao tác. Phù hợp để học, không phù hợp để dùng thật.
Sắp xếp nhanh Quicksort
Chọn một phần tử làm chốt, chia danh sách thành hai nhóm: nhỏ hơn chốt và lớn hơn chốt, rồi đệ quy sắp xếp từng nhóm. Trung bình O(n log n), nhanh hơn hẳn nổi bọt, và là thuật toán sắp xếp được dùng rộng rãi nhất trong thực tế — kể cả trong thư viện chuẩn của nhiều ngôn ngữ lập trình.
Thuật toán trong đời sống thực
- Google Maps dùng thuật toán tìm đường ngắn nhất (nổi tiếng nhất là Dijkstra) để tính tuyến đường tối ưu giữa hàng triệu nút giao thông.
- Netflix, YouTube dùng thuật toán gợi ý để dự đoán nội dung bạn thích dựa trên lịch sử xem và người dùng tương tự.
- Ngân hàng dùng thuật toán kiểm tra số dư, xác thực giao dịch trong tích tắc để bạn rút tiền không phải chờ đợi.
- Tìm kiếm Google là tổ hợp hàng trăm thuật toán xếp hạng hàng tỷ trang web chỉ trong chưa đầy một giây.
Học thuật toán như thế nào?
Đừng bắt đầu bằng sách lý thuyết dày cộp. Lộ trình thực tế cho người mới:
- Nắm vững một ngôn ngữ lập trình cơ bản như Python để viết được mã chạy thật.
- Làm quen với cấu trúc dữ liệu nền tảng: mảng, danh sách liên kết, ngăn xếp, hàng đợi, bảng băm.
- Thực hành tìm kiếm nhị phân và sắp xếp nhanh bằng tay trên giấy trước khi viết code.
- Giải bài tập trên các nền tảng luyện thuật toán để phản xạ.
- Học cách ước lượng Big-O cho chính code của mình sau mỗi bài tập.
Nguyên tắc vàng: viết trước, tối ưu sau. Đừng cố tối ưu một chương trình chạy trên 100 phần tử, hãy tập trung viết đúng rồi mới tính đến chuyện làm nhanh.
Tổng kết
Thuật toán là nền tảng của mọi phần mềm hiện đại. Nắm được khái niệm Big-O, tìm kiếm nhị phân và Quicksort, bạn đã có nền móng đủ vững để học tiếp các chủ đề nâng cao như cấu trúc dữ liệu phức tạp, đồ thị và trí tuệ nhân tạo. Quan trọng nhất: hãy viết code thật, giải bài tập thật, vì thuật toán chỉ ngấm vào người qua thực hành.
Tham khảo thêm
Khóa học thuật toán miễn phí của Khan Academy · Big-O Notation giải thích dễ hiểu (freeCodeCamp) · Tổng hợp thuật toán cơ bản (GeeksforGeeks)
