Nội dung bài viết
Xã hội hiện tại đang chứng kiến một cuộc cách mạng to lớn trong lĩnh vực công nghệ. Những phát minh mới liên tục được cập nhật. Thường thì nguồn gốc của những phát minh này là từ những chương trình gạo cội có khả năng chi phối và thao túng các xu hướng công nghệ đang diễn ra. Trong số đó không thể không nói đến mã hóa và thuật toán, được sử dụng để phát triển các chương trình cạnh tranh như vậy.
Vì thế, đối với một chương trình thành công và có tầm ảnh hưởng, việc khai thác một thuật toán tốt nhất đúng và chính xác là điều tất yếu. Sau đây là 9 thuật toán hàng đầu được sử dụng rộng rãi trong lập trình và phát triển web.
1. Search Algorithms
Thuật toán tìm kiếm áp dụng cho hai loại cấu trúc dữ liệu: dạng tuyến tính (mảng, danh sách) và dạng đồ thị (graph, cây).
Tìm kiếm tuyến tính (linear search) duyệt lần lượt từng phần tử cho đến khi gặp giá trị cần tìm. Nó không đòi hỏi dữ liệu phải sắp xếp trước, đổi lại độ phức tạp là O(n).
Tìm kiếm nhị phân (binary search) là một thuật toán khác hẳn, chỉ chạy được trên dữ liệu đã sắp xếp. Nó liên tục chia đôi phạm vi tìm kiếm nên độ phức tạp chỉ O(log n). Đây cũng chính là ý tưởng đằng sau git bisect: chia đôi lịch sử commit để tìm ra commit gây lỗi chỉ trong vài bước thay vì kiểm tra từng commit một.
Với đồ thị và cây, hai thuật toán nền tảng là DFS (Depth First Search, duyệt theo chiều sâu) và BFS (Breadth First Search, duyệt theo chiều rộng). BFS duyệt theo từng lớp nên tìm được đường đi ngắn nhất trên đồ thị không trọng số, được dùng nhiều trong bài toán tìm đường và trong các công cụ thu thập dữ liệu web.
2. Thuật toán sắp xếp (Sort Algorithms)
Thuật toán sắp xếp đưa dữ liệu về một thứ tự xác định. QuickSort so sánh các phần tử với nhau để xác định thứ tự, đạt O(n log n) ở trường hợp trung bình nhưng có thể tụt xuống O(n²) nếu chọn pivot không tốt. MergeSort giữ được O(n log n) trong mọi trường hợp và ổn định, đổi lại tốn thêm bộ nhớ.
Radix Sort đạt O(n·k) với k là số chữ số của khóa, nghe thì nhanh hơn nhưng nó không phải lựa chọn thay thế phổ quát: chỉ dùng được khi khóa là số nguyên hoặc chuỗi có độ dài cố định, và hằng số thực tế thường lớn. Nói cách khác, không có chuyện Radix Sort luôn nhanh hơn QuickSort, chọn cái nào phải nhìn vào kiểu dữ liệu.
Trong thực tế thì hiếm khi bạn phải tự cài đặt: hàm sắp xếp có sẵn của mọi ngôn ngữ đều đã dùng thuật toán lai (Timsort trong Python và Java, introsort trong C++). Hiểu chúng chủ yếu để biết khi nào cần cấu trúc dữ liệu khác thay vì sắp xếp lại từ đầu.
3. Thuật toán lập trình động (Dynamic Programming Algorithms)
Lập trình động thường là một hàm giải quyết vấn đề phức tạp liên quan đến trí tuệ bằng cách tách các vấn đề thành các bài toán con nhỏ hơn, giải quyết chúng sau đó xây dựng trở lại thành vấn đề phức tạp với bộ nhớ của các kết quả nhỏ hơn để đưa ra câu trả lời cho vấn đề phức tạp ban đầu. Lập trình động có khả năng tích hợp để ghi nhớ, cho phép lưu trữ các ký ức về các vấn đề đã giải quyết trước đó. Nếu lần tiếp theo vấn đề ấy lại xuất hiện thì nó sẽ được giải quyết nhanh hơn nhiều.
4. Phân tích liên kết (Link Analysis)
Thường được sử dụng trong lĩnh vực mạng, phân tích liên kết cung cấp khả năng tương quan giữa các thực thể khác nhau trong một miền quan trọng đối với các công cụ tìm kiếm. Thuật toán sử dụng một biểu diễn đồ họa và ma trận phức tạp, liên kết các căn cứ tương tự trong các miền hiện tại. Phân tích liên kết phổ biến trong các công cụ tìm kiếm như Google, trong các trang truyền thông xã hội như Facebook, Twitter, nơi việc tìm kiếm mở rộng được chú trọng.
5. Phép toán Mô-đun (Modulo Arithmetic Algorithms)
Nhiều thuật toán mã hóa phức tạp nhưng nếu được phân tích trên nền số học mô-đun thì trở nên đơn giản vô cùng. Trong số học mô-đun, các số chúng ta đang xử lý chỉ là các số nguyên và các phép toán được sử dụng là cộng, trừ, nhân và chia. Sự khác biệt duy nhất giữa số học mô-đun và số học trên sách vở là trong số học mô-đun, tất cả các hoạt động được thực hiện liên quan đến số nguyên dương, tức là mô đun.
Ví dụ:
- Thuật toán Euclid cơ bản và Euclid mở rộng
- Định lý Euler và hàm phi Euler (Euler’s totient)
- Lũy thừa modulo (modular exponentiation)
- Nghịch đảo modulo (modular multiplicative inverse)
- Định lý số dư Trung Hoa (Chinese Remainder Theorem)
6. Thuật toán xâu ký tự và phân tích cú pháp (String Matching and Parsing Algorithms)
Quy trình tạo xâu tương ứng luôn quan trọng đặc biệt đối với miền và phần tử mạng. Thuật toán xâu ký tự này sẽ phát huy khả năng tối đa trong các tình huống mà các xâu phải khớp trong một chuỗi dài hoặc khi xác nhận chuỗi bằng cách phân tích cú pháp qua giới hạn được xác định trước. Các thuật toán này thường được sử dụng trong phát triển web cho URL.
7. Thuật toán biến đổi Fourier (Fourier Transform Algorithms)
Biến đổi Fourier hay Biến đổi Fourire nhanh là những thuật toán đơn giản nhưng rất mạnh. Chúng được sử dụng để chuyển đổi tín hiệu từ miền thời gian sang miền tần số và ngược lại. Toàn bộ các mạng kỹ thuật số như Internet, WiFi, điện thoại, máy tính, bộ định tuyến, vệ tinh, sử dụng thuật toán này theo để vận hành. Đây là những thuật toán bắt buộc phải biết nếu bạn chuyên sâu về mảng điện tử, điện toán hoặc viễn thông.
8. Thuật toán các tập không giao nhau (Disjoint Sets)
Thuật toán các tập không giao nhau là cấu trúc dữ liệu đóng vai trò như các cấu trúc trợ giúp trong một thuật toán để biểu diễn nhiều tập hợp trong mảng riêng lẻ, với mỗi mục là một phần tử của một trong nhiều tập hợp. Do đó, các bộ tách rời đại diện cho các phần tử được kết nối trong các thuật toán đồ thị hay phân đoạn một hình ảnh.
9. Phân tích thừa số nguyên tố (Integer Factorization)
Phân tích thừa số nguyên tố là bài toán tách một hợp số thành tích các số nguyên tố. Điều đáng nói là cho đến nay chưa ai tìm được thuật toán chạy trong thời gian đa thức trên máy tính cổ điển để làm việc này với số đủ lớn, và chính sự khó đó là nền tảng bảo mật của RSA: nhân hai số nguyên tố lớn thì dễ, tách ngược lại thì gần như bất khả thi.
Đây cũng là lý do máy tính lượng tử được quan tâm: thuật toán Shor giải được bài toán này trong thời gian đa thức, nên nếu máy tính lượng tử đủ lớn xuất hiện thì RSA sẽ không còn an toàn.
Trên đây là 9 thuật toán trong lập trình mà mình đã giới thiệu với mọi người. Nếu bạn muốn trở thành lập trình viên thì đây là những thuật toán không thể bỏ qua.
