Thuật toán là gì¶
Định nghĩa thuật toán¶
Thuật toán (algorithm) là một tập hợp các chỉ thị hoặc các bước thao tác nhằm giải quyết một vấn đề cụ thể trong một khoảng thời gian hữu hạn. Nó có các đặc trưng sau.
- Vấn đề được xác định rõ ràng, đi kèm định nghĩa rõ ràng về đầu vào (input) và đầu ra (output).
- Có tính khả thi, có thể hoàn thành trong số bước, thời gian và không gian bộ nhớ hữu hạn.
- Mỗi bước đều có ý nghĩa xác định; dưới cùng một điều kiện đầu vào và vận hành, đầu ra luôn giống nhau.
Định nghĩa cấu trúc dữ liệu¶
Cấu trúc dữ liệu (data structure) là cách thức tổ chức và lưu trữ dữ liệu, bao gồm nội dung dữ liệu, mối quan hệ giữa các phần tử dữ liệu và phương thức thao tác trên chúng. Nó có các mục tiêu thiết kế sau.
- Chiếm dụng càng ít không gian càng tốt để tiết kiệm bộ nhớ máy tính.
- Thao tác dữ liệu nhanh nhất có thể, bao gồm truy cập, thêm, xóa, cập nhật dữ liệu, v.v.
- Cung cấp biểu diễn dữ liệu và thông tin logic ngắn gọn để thuật toán hoạt động hiệu quả.
Thiết kế cấu trúc dữ liệu là một quá trình đầy sự đánh đổi. Nếu muốn cải thiện ở khía cạnh này, chúng ta thường phải chấp nhận đánh đổi ở khía cạnh khác. Dưới đây là hai ví dụ.
- So với mảng (array), danh sách liên kết (linked list) thuận tiện hơn cho các thao tác thêm và xóa dữ liệu nhưng phải đánh đổi bằng tốc độ truy cập dữ liệu.
- So với danh sách liên kết, đồ thị (graph) cung cấp thông tin logic phong phú hơn nhưng đòi hỏi không gian bộ nhớ lớn hơn.
Mối quan hệ giữa cấu trúc dữ liệu và thuật toán¶
Như hình dưới đây, cấu trúc dữ liệu và thuật toán có mối liên hệ mật thiết và gắn kết chặt chẽ với nhau, thể hiện cụ thể ở ba khía cạnh sau.
- Cấu trúc dữ liệu là nền tảng của thuật toán. Cấu trúc dữ liệu cung cấp dữ liệu được lưu trữ có cấu trúc và các phương thức thao tác dữ liệu cho thuật toán.
- Thuật toán thổi hồn vào cấu trúc dữ liệu. Bản thân cấu trúc dữ liệu chỉ lưu trữ thông tin dữ liệu; chỉ khi kết hợp với thuật toán, chúng mới có thể giải quyết các vấn đề cụ thể.
- Thuật toán thường có thể được triển khai dựa trên các cấu trúc dữ liệu khác nhau, nhưng hiệu suất thực thi có thể khác biệt rất lớn. Việc lựa chọn cấu trúc dữ liệu phù hợp là chìa khóa.
Cấu trúc dữ liệu và thuật toán giống như trò chơi lắp ráp mô hình ở hình dưới đây. Một bộ đồ chơi lắp ráp, ngoài việc bao gồm nhiều chi tiết, còn đi kèm với sách hướng dẫn lắp ráp chi tiết. Chúng ta làm theo từng bước hướng dẫn là có thể lắp ráp thành một mô hình tinh xảo.
Mối liên hệ chi tiết giữa hai thành phần được thể hiện ở bảng dưới đây.
Bảng
| Cấu trúc dữ liệu và thuật toán | Lắp ráp mô hình |
|---|---|
| Dữ liệu đầu vào | Các mảnh ghép chưa lắp ráp |
| Cấu trúc dữ liệu | Hình thức tổ chức mảnh ghép, bao gồm hình dạng, kích thước, phương thức liên kết, v.v. |
| Thuật toán | Một chuỗi các bước thao tác để lắp ráp các mảnh ghép thành hình dạng mục tiêu |
| Dữ liệu đầu ra | Mô hình hoàn chỉnh |
Cần lưu ý rằng cấu trúc dữ liệu và thuật toán độc lập với ngôn ngữ lập trình. Chính vì vậy, cuốn sách này có thể cung cấp các triển khai dựa trên nhiều ngôn ngữ lập trình khác nhau.
Quy ước gọi tắt
Trong các cuộc thảo luận thực tế, chúng ta thường rút gọn cụm từ "cấu trúc dữ liệu và thuật toán" thành "thuật toán". Ví dụ như các bài toán thuật toán LeetCode nổi tiếng thực chất là kiểm tra kiến thức về cả cấu trúc dữ liệu lẫn thuật toán.