Chuẩn bị những gì để học thuật toán?
Đầu tiên, để học được “cấu trúc dữ liệu và giải thuật” (thuật toán), các bạn cần phải có khả năng tự học cao. Hầu hết mọi thứ cơ bản đều có trên google, nhưng trong bài viết này mình sẽ đưa ra những vấn đề quan trọng để bạn tìm kiếm một nền tảng vững chắc.
Bạn đang xem: Lộ Trình Học Cấu Trúc Dữ Liệu Và Giải Thuật (Phần 1)
Tiếp theo, bạn cần chọn cho mình một ngôn ngữ lập trình. Theo mình thì C/C++ là ngôn ngữ nên được sử dụng khi học thuật toán vì:
- Các kiểu dữ liệu trong ngôn ngữ C/C++ được định nghĩa rõ ràng, có kiểu truyền tham chiếu và tham trị khá hay.
- Tốc độ thực thi nhanh.
- Có nhiều sách, tài liệu tham khảo trên internet về cấu trúc dữ liệu và giải thuật được viết bằng C/C++.
Tuy nhiên, nếu bạn muốn hoặc có nền tảng các ngôn ngữ khác (java, python,…) thì bạn cũng có thể sử dụng để học được vì công thức sau:
Cấu trúc dữ liệu + Giải thuật = Chương trình
Việc viết một chương trình, giải một bài toán được kết hợp bởi 2 yếu tố, lựa chọn một cấu trúc dữ liệu phù hợp, sau đó tìm ra phương hướng kết hợp mọi thứ bằng giải thuật để có thể giải được bài toán. Do đó bạn có thể lựa chọn ngôn ngữ yêu thích và bắt đầu.
Contents
Các vấn đề cần quan tâm
Xem thêm : Tổng hợp full bộ tài liệu C++ cơ bản dành cho người mới bắt đầu
Trong phần này mình sẽ nói về 7 vấn đề sau:
1. Độ phức tạp thuật toán (big O)
Khái niệm độ phức tạp thuật toán có thể hiểu đơn giản là độ nhanh hay chậm của thuật toán. Chữ O là ký hiệu được sử dụng cho độ phức tạp thuật toán. Các loại độ phức tạp thuật toán cơ bản có thể kể đến là:
- O(1): Thời gian thực hiện không phụ thuộc vào kích thước đầu vào.
- O(n): Thời gian thực hiện tuyến tính, phụ thuộc vào kích thước đầu vào.
- O(n^2): Thời gian thực hiện tuyến tính bình phương, phụ thuộc vào bình phương của kích thước đầu vào.
- O(log(n)): Thời gian thực hiện tăng theo logarit của kích thước đầu vào.
- O(nlog(n)): Thời gian thực hiện tăng theo tích của kích thước đầu vào và logarit của kích thước đầu vào.
Và còn nhiều loại độ phức tạp thuật toán khác nữa. Lưu ý rằng độ phức tạp thuật toán là một xấp xỉ và thường được tính ước lượng dựa trên kịch bản tốt nhất.
2. Sắp xếp và tìm kiếm nhị phân
a. Sắp xếp
Để hiểu rõ các thuật toán sắp xếp, bạn nên tìm các mã nguồn trên mạng và chạy thử, sau đó tự ngẫm xem cách chúng chạy và các phép toán có tác dụng gì. Trong các thuật toán sắp xếp, mình thấy có rất nhiều thuật toán như: Bubble sort, Selection sort, Insertion sort, Quick sort, Heap sort,…
Mình khuyến nghị bạn học các thuật toán Bubble sort (O(n)) và Quick sort (~O(nlog(n))) để làm bài tập và code thuật toán. Đa số đều sử dụng Quick sort hoặc hàm sort trong thư viện (Trong C++ là hàm sort trong thư viện algorithm có độ phức tạp ~O(nlog(n))).
b. Tìm kiếm nhị phân
Ý tưởng chính của tìm kiếm nhị phân có thể biểu diễn đơn giản bằng một bài toán như sau:
Xem thêm : 8 tài liệu học ngôn ngữ lập trình Python cơ bản – nâng cao bạn nên đọc
Có n bạn được xếp thành một hàng theo thứ tự chiều cao tăng dần. Thầy giáo nhìn vào danh sách học sinh mà không có tên, chỉ có chiều cao, do đó cần tìm bạn có chiều cao là X trong hàng.
Phương pháp tìm kiếm nhị phân giúp tìm kiếm một phần tử trong một dãy đã được sắp xếp. Với cách này, ta chỉ cần so sánh phần tử ở giữa với giá trị cần tìm, nếu bằng nhau, ta đã tìm thấy. Nếu nhỏ hơn, ta tiếp tục tìm kiếm trong nửa phía trước của dãy, nếu lớn hơn, ta tiếp tục tìm kiếm trong nửa phía sau của dãy, và tiếp tục thực hiện quy trình này cho đến khi tìm thấy hoặc không tìm thấy phần tử cần tìm.
3. Các phương pháp sinh
Có thể bạn chưa biết, gần như tất cả các bài toán đều có thể được giải bằng cách duyệt trâu từng trường hợp. Do đó, các phương pháp sinh là không thể thiếu khi học thuật toán. Có 4 phương pháp sinh mà bạn nhất định phải học: Sinh nhị phân, Sinh hoán vị, Sinh tổ hợp, Sinh chỉnh hợp.
4. Đệ quy, quay lui
Đệ quy là việc một hàm gọi lại chính nó. Nó biểu diễn đối tượng được định nghĩa theo các đối tượng con đồng dạng với nó. Một số ví dụ của hàm đệ quy:
int giaithua(int n) {
int res = 1;
for (int i = 1; i <= n; i++) {
res *= i;
}
return res;
}
int giaithua(int n) {
if (n == 0) return 1;
return n * giaithua(n-1);
}
int f[100];
int fibo(int n) {
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
int f[100];
int fibo(int n) {
if (n == 0 || n == 1) return f[n] = 1;
if (f[n]) return f[n];
return f[n] = fibo(n-1) + fibo(n-2);
}
Qua đó, các bạn có thể thấy các hàm đệ quy rất thú vị. Các phương pháp sinh có thể dùng để duyệt hết các cấu hình có thể. Trong một số bài toán, có thể sử dụng nhánh cận, cài cắm các đoạn xử lý loại bỏ các trường hợp không cần thiết để tối ưu hơn.
Tạm kết
Ở đây, mình tạm dừng phần 1. Trong bài viết tiếp theo, mình sẽ nói tiếp về các vấn đề cần quan tâm khác, các nguồn tài liệu và trang web mình hay dùng trong quá trình học. Các bạn đón xem nhé :))
Nguồn: https://laptrinhc.edu.vn
Danh mục: Tài liệu IT