Học cấu trúc dữ liệu và giải thuật luôn được xem là bộ môn rất quan trọng đối với bất cứ sinh viên công nghệ thông tin nào. Để có thể làm tốt những công việc trong tương lai bạn phải nắm vững nó càng chắc càng tốt. Sau đây, chúng ta sẽ cùng tìm hiểu chi tiết hơn về môn học này.
1. Cấu trúc dữ liệu và giải thuật là gì?
Cùng tìm hiểu lần lượt định nghĩa của hai khái niệm “cấu trúc dữ liệu” và “giải thuật” nhé.
1.1. Cấu trúc dữ liệu [Data structure]
Khi dữ liệu được lưu trữ, tổ chức một cách logic mà qua đó bạn có thể được sử dụng và quản lý một cách hiệu quả thì người ta gọi đó là cấu trúc dữ liệu. Ví dụ khi bạn tháo một thiết bị điện tử nào đó và đặt chúng theo thứ tự khi được tháo ra. Sau đó lắp lại theo thứ tự ngược lại thì cũng gọi là cấu trúc dữ liệu.
Nguyên tắc khi sử dụng dữ liệu vào sau sẽ được lấy ra trước là nguyên tắc của một loại cấu trúc dữ liệu khi hoạt động. Tùy vào từng trường hợp mà ta có rất nhiều loại cấu trúc dữ liệu khác nhau và mỗi loại sẽ có những ưu nhược điểm riêng.
Không có một cấu trúc dữ liệu nào được gọi là hoàn hảo. Tùy vào từng trường hợp cụ thể, ta sẽ ứng dụng cấu trúc khác nhau sao cho hiệu quả mang lại là tối ưu nhất.
1.2. Giải thuật [Algorithms]
Giải thuật hay còn gọi là thuật toán, trong tiếng Anh là Algorithms. Nó có nghĩa là tập hợp các thao tác, các bước để giải quyết một vấn đề gì đó hiệu quả hơn.
Ví dụ, khi bạn nấu cơm sẽ bao gồm các bước là: Lấy gạo – vo gạo – đong nước – đặt vào nồi – cắm điện – bật nút – đợi cơm chín. Các bước này chính là giải thuật nấu cơm. Tương tự trong lập trình có nhiều giải thuật hay còn gọi là thuật toán khác nhau giúp giải quyết các vấn đề trong lập trình.
2. Tầm quan trọng của việc học cấu trúc dữ liệu và giải thuật
Ta có thể thấy không chỉ các ngôn ngữ lập trình như Java, PHP, Python,… mà bất kể bạn dùng ngôn ngữ nào, bạn đều cần biết về cấu trúc dữ liệu và giải thuật để giải quyết vấn đề. Ngôn ngữ chỉ là một công cụ, còn cấu trúc dữ liệu và giải thuật là phương pháp. Do đó, cấu trúc dữ liệu và giải thuật đóng một vai trò rất quan trọng trong lập trình.
Có một thực tế là trong quá trình tuyển dụng, một trong những yếu tố đầu tiên nhà tuyển dụng xem xét chính là kỹ năng về cấu trúc dữ liệu và giải thuật, sau đó mới đến ngôn ngữ lập trình mà bạn có thể sử dụng. Và đương nhiên, bạn sẽ phải nắm vững cả 2 yếu tố trên để có thể đáp ứng được yêu cầu của công việc.
Chính vì thế việc học cấu trúc dữ liệu và giải thuật là vô cùng quan trọng trong những ngành này. Tương lai ngoài viết code ra, bạn còn có thể trở thành người thiết kế phần mềm hoặc team leader quản lý dự án nếu kiên trì tập luyện và không ngừng nâng cao kỹ năng của mình.
Vì vậy, các bạn sinh viên đang theo học công nghệ thông tin không thể bỏ qua môn học bổ ích này. Việc nghiên cứu và học cấu trúc dữ liệu và giải thuật sẽ giúp ích rất nhiều trong công việc của bạn ở hiện tại và tương lai.
Cấu trúc dữ liệu [data structure] là cách thức tổ chức dữ liệu sao cho phù hợp với bài toán và có thể dùng máy tính để xử lý các dữ liệu đó một cách hiệu quả.
Các tiêu chuẩn của một cấu trúc dữ liệu:
- Phải biểu diễn đầy đủ thông tin
- Phải phù hợp với các thao tác xử lý
- Phù hợp với điều kiện cho phép của ngôn ngữ lập trình
- Tiết kiệm được tài nguyên hệ thống
Có nhiều loại cấu trúc dữ liệu nhưng có thể chia thành 2 loại: cấu trúc dữ liệu tuyến tính [linear] và phi tuyến tính [non-linear].
Giải thuật là tên gọi khác của thuật toán. Thuật toán [algorithm] là tập hợp hữu hạn các thao tác được định nghĩa rõ ràng nhằm giải quyết một bài toán cụ thể nào đó.
Một thuật toán phải đảm bảo 5 tính chất sau:
– Tính chính xác: quá trình tính toán hay các thao tác máy tính thực hiện là chính xác.
– Tính rõ ràng: các câu lệnh minh bạch được sắp xếp theo thứ tự nhất định.
– Tính khách quan: được viết bởi nhiều người trên máy tính nhưng kết quả phải như nhau.
– Tính phổ dụng: có thể áp dụng cho một lớp các bài toán có đầu vào tương tự nhau.
– Tính kết thúc: hữu hạn các bước tính toán.
Các bạn có thể đọc thêm bài Thuật toán là gì? Các phương pháp biểu diễn thuật toán để hiểu rõ hơn về thuật toán.
Thuật toán và cấu trúc dữ liệu có mối quan hệ chặt chẽ với nhau. Cuốn sách “Algorithms + Data Structures = Programs” là một trong những cuốn sách kinh điển của nhà khoa học máy tính Niklaus Wirth viết vào năm 1976 nói lên điều đó.
Thật vậy, bất kỳ một chương trình nào cũng cần có dữ liệu để tính toán, xử lý. Nhiệm vụ tính toán, xử lý sẽ được giao cho thuật toán. Để chương trình hoạt động tốt, ổn định thì thuật toán phải xử lý tốt và chính xác trên dữ liệu. Do đó, những dữ liệu này cần được lưu trữ, tổ chức một cách hợp lý với thuật toán.
Rõ ràng, cấu trúc dữ liệu đóng vai trò quan trọng trong việc kết hợp và đưa ra cách giải quyết bài toán. Cấu trúc dữ liệu cũng hỗ trợ cho các thuật toán thao tác, xử lý hiệu quả hơn.
Với một bài toán, chúng ta có thể có nhiều thuật toán để giải quyết bài toán đó. Nhưng một câu hỏi đặt ra là thuật toán nào tốt hơn thuật toán nào? Để trả lời câu hỏi này, cần xem xét thế nào là một thuật toán hiệu quả?
Một thuật toán hiệu quả thì chi phí sử dụng tài nguyên như bộ nhớ, thời gian sử dụng CPU,… thấp. Người ta thường phân tích độ phức tạp thuật toán để đánh giá sự hiệu quả của thuật toán. Có hai phương pháp đánh giá độ phức tạp của thuật toán là:
- Phương pháp thực nghiệm
- Phương pháp xấp xỉ toán học
Phương pháp thực nghiệm
Cài thuật toán rồi chọn các bộ dữ liệu thử nghiệm. Chạy thuật toán rồi thống kê các thông số [thời gian chạy thuật toán, dung lượng bộ nhớ,…] khi chạy thuật toán với các bộ dữ liệu đó.
Ưu điểm: Dễ thực hiện.
Nhược điểm:
- Chịu sự hạn chế của ngôn ngữ lập trình
- Ảnh hưởng bởi trình độ của người lập trình
- Chọn được các bộ dữ liệu thử đặc trưng cho tất cả tập các dữ liệu đầu vào của thuật toán thì khó khăn và tốn nhiều chi phí
- Phụ thuộc vào phần cứng
Trong nghiên cứu khoa học, phương pháp này được sử dụng rất nhiều.
Phương pháp xấp xỉ toán học
Đánh giá độ phức tạp thuật toán theo hướng xấp xỉ tiệm cận qua các khái niệm O[]. Hiểu đơn giản là xấp xỉ số lần thực hiện các phép toán của thuật toán. Số lần thực hiện phép toán càng ít thì thuật toán càng ít phức tạp [càng tốt] và ngược lại.
Ưu điểm: Ít phụ thuộc ngôn ngữ lập trình cũng như phần cứng hơn.
Nhược điểm: Cách tính phức tạp, cần có kiến thức toán học.
Người ta sử dụng các ký hiệu BigO bên dưới để đánh giá độ phức tạp thuật toán theo độ phức tạp tăng dần.
- Hằng số: O[c]
- logN: O[logN]
- N: O[N]
- NlogN: O[NlogN]
- N2: O[N2]
- N3: O[N3]
- 2N: O[2N]
- N!: O[N!]