Lộ Trình Học Cấu Trúc Dữ Liệu Và Giải Thuật (Phần 1)

Đối với người học lập trình nói chung, cấu trúc dữ liệu và giải thuật là một trong những môn quan trọng và thường được dạy vào khoảng năm 2 và năm 3 đại học. Cảm giác của rất nhiều bạn nếu chưa tự tin là dễ bị nản ngay từ giai đoạn đầu và dần dần sẽ khó khăn hơn để bắt nhịp. Đồng thời, học tốt cấu trúc dữ liệu và giải thuật sẽ giúp cho các dòng code của mình trở nên tối ưu hơn.

Trong bài viết này, mình sẽ tổng hợp những kiến thức và kỹ năng cơ bản cùng những kinh nghiệm tay nghề của mình để giúp những bạn đi đúng hướng và cảm thấy sự mê hoặc của môn học này. Tất nhiên xung quanh ta vẫn có rất nhiều cao thủ, việc ra mắt những kỹ năng và kiến thức khó sẽ khiến mọi người bị ngợp nên trong khoanh vùng phạm vi bài viết này, mình sẽ trình làng những yếu tố cơ bản ( tối thiểu là trong những bài kiểm tra trên trường ). Hãy cùng tìm hiểu thêm bài viết dưới đây :

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 (Từ giờ đến cuối bài viết mình sẽ gọi tắt là thuật toán), các bạn cần phải có khả năng tự học cao. Phải có khả năng tìm kiếm tốt. Hầu hết mọi thứ cơ bản đều có trên google, trong khuôn khổ bài viết này mình sẽ đưa ra các vấn đề quan trọng, để các bạn follow theo keyword đó, tìm kiếm cho mình một nền tảng vững chắc.

Tiếp theo, các 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ì:

Bạn đang đọc: Lộ Trình Học Cấu Trúc Dữ Liệu Và Giải Thuật (Phần 1)

• 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 muốn hoặc có nền tảng những ngôn từ khác ( java, python, … ) thì mọi người cũng hoàn toàn có thể sử dụng để học được vì theo 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.

Các vấn đề cần quan tâm

Trong phần này mình sẽ nói về 7 yếu tố sau :
1. Độ phức tạp thuật toán ( big O )
2. Sắp xếp và tìm kiếm nhị phân
3. Các giải pháp sinh
4. Đệ quy, quay lui
5. Cấu trúc dữ liệu stack, queue, dequeue
6. Quy hoạch động
7. Đồ thị .

1. Độ phức tạp thuật toán (big O)

Khái niệm độ phức tạp thuật toán hoàn toàn có thể hiểu đơn thuầ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 hoàn toàn có thể kể đến là :

Xem thêm: Thao tác nào sau đây không là khai thác cơ sở dữ liệu quan hệ?

Trong đó, n là biểu lộ kích cỡ nguồn vào .
Lưu ý rằng nếu những bạn sử dụng 2 vòng lặp cùng cấp thì kích cỡ sẽ là 2 * n, nhưng độ phức tạp thuật toán trình diễn vẫn là O ( n ) vì mình chỉ lấy xê dịch thôi .
Và nếu bạn của bạn nói là 2 vòng lặp lồng nhau thì độ phức tạp sẽ là O ( n ^ 2 ) thì tất cả chúng ta nhiều lúc phải xem xét kỹ hơn thuật toán. Như ví dụ sau :

int i = 0;
int n = 1000;
while (i < n/2) {
	i++;
	// Do somethings in O(1)
	if (i < n/2) continue;
	while (i < n) {
		i++;
		// Do somethings in O(1)
	}
}

Nếu không chú ý thì hoàn toàn có thể sẽ nhầm hàm này là O ( N ^ 2 ), nhưng thực tế độ phức tạp của nó là O ( n ). Bởi vì nếu như i < n / 2 thì hàm sẽ chỉ lặp 1 lần và không nhảy xuống dưới, còn khi i bằng n / 2 thì vòng lặp while bên dưới sẽ lặp cho đến khi i bằng n rồi sau đó sẽ thoát ra khỏi cả 2 vòng lặp, do đó độ phức tạp chỉ là O ( n ) .

2. Sắp xếp và tìm kiếm nhị phân

a. Sắp xếp

Để hoàn toàn có thể hiểu rõ những thuật toán chạy như nào, những bạn nên tìm những source code trên mạng về và chạy thử, sau đó tự ngẫm xem những hàm của nó chạy như nào, những phép toán có tính năng gì. Trong những thuật toán sắp xếp thì mình thấy có rất nhiều thuật toán như :

• Bubble sort
• Selection sort
• Insertion sort
• Quick sort
• Heap sort
• ...

Ngoài ra còn rất nhiều thuật toán sắp xếp khác nữa, tùy vào điều kiện kèm theo môn học trên trường nhu yếu gì thì mình học theo. Còn theo kinh nghiệm tay nghề của mình thì để làm bài tập và code thuật toán thì học bubble sort ( O ( n ) ) và quick sort ( ~ O ( nlog ( n ) ) ) thôi là đủ code được cả nghìn bài rồi. Đa số đều sử dụng quick sort hay dùng luôn 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 ) ) ) .

Còn việc giới thiệu nhiều thuật toán sort là tùy từng điều kiện cụ thể thì từng thuật toán có những ưu điểm và khuyết điểm riêng, ứng dụng trong thực tế. ví dụ như insertion sort hay sắp xếp chèn thường được sử dụng trong bảng xếp hạng,đây là thuật toán sắp xếp xử lý chèn phần tử đang xét vào vị trí thích hợp của dãy số đã sắp xếp phía trước sao cho dãy số vẫn là dãy sắp xếp có thứ tự. 

b. Tìm kiếm nhị phân

Ý tưởng chính của tìm kiếm hoàn toàn có thể màn biểu diễn đơn thuần bằng một bài toán như sau :
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 list học viên mà không có tên, chỉ có độ cao, do đó cần tìm bạn có chiều cao là X trong hàng .
Bình thường thì cách làm đơn thuần nhất là duyệt từ đầu hàng đến cuối hàng một cách lần lượt, khi đó chắc như đinh sẽ tìm được bạn có chiều cao là X đó ( độ phức tạp thuật toán sẽ là O ( n ) ). Có một cách nhanh hơn để giải bài toán này, đó là ta sẽ nhìn vào người ở giữa dãy, nếu bạn đó có chiều cao bằng X thì ta sẽ tìm được luôn, còn nếu không thì ta sẽ biết chắc như đinh người đó sẽ đứng ở nửa nào trong 2 nửa còn lại của hàng, qua đó lặp lại giải pháp trên đến khi tìm ra bạn đó, đây chính là sáng tạo độc đáo chính của thuật toán tìm kiếm nhị phân với độ phức tạp chỉ còn O ( nlog ( n ) ) .

3. Các phương pháp sinh

Có thể bạn chưa biết, gần như là tổng thể những bài toán đều hoàn toàn có thể giải bằng cách duyệt trâu từng trường hợp. Do đó những giải pháp sinh là không hề thiếu khi học thuật toán. Có 4 chiêu thức sinh mà những 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

Các bạn hoàn toàn có thể khám phá những thuật toán trên và submit trong trang sau nhé :
https://www.spoj.com/PTIT/problems/basic/

4. Đệ quy, quay lui

Nói đơn giản thì đệ quy là hàm gọi lại chính nó, biểu diễn đối tượng được định nghĩa quy nạp theo các đối tượng con đồng dạng với nó. Sau đây là một số ví dụ của hàm sử dụng vòng lặp bình thường và hàm đệ quy:

Xem thêm: Tìm việc Làm Giám đốc Đầu tư và Phát triển Dự án Tuyển Dụng 19/04/2023 | https://thomaygiat.com

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-1];
	}
	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);
}

Bây giờ hãy cùng mình xem qua 1 số ít cách viết hàm tính a ^ b ( với a khác 0 ). Tất nhiên với những bài toán số lượng giới hạn lớn thì a ^ b sẽ rất lớn, do đó mình sẽ lấy phần dư cho mod nhé .

// dpt O(n)
long long cal_pow(int a, int b, int mod) {
	long long res=1;
	for (int i = 1; i <= b; i++) {
		res = res * a % mod;
	}
	return res;
}

// dpt O(log(n))
long long cal_pow(int a, int b, int mod) {
	if (b == 0) return 1;
	long long res;
	if (b % 2 == 1) {
		res = 1ll * a * cal_pow(a, b-1, mod) % mod;
	}
	else {
		long long num = cal_pow(a, b/2, mod);
		res = num * num % mod;
	}
	return res;
}

// vẫn là dpt O(log(n)) nhưng viết ngắn hơn
long long cal_pow(int a, int b, int mod) {
	if (b == 0) return 1;
	if (b & 1) return 1ll * a * cal_pow(a, b-1, mod) % mod;
	return cal_pow(1ll * a * a % mod, b >> 1, mod);
}

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 ở trên, ngoài cách code chay sinh từng cấu hình thì cũng có thể sử dụng đệ quy để viết một cách gọn gàng hơn. Thuật toán quay lui cũng dựa trên tư tưởng của hàm đệ quy như trên, suy cho cùng các thuật toán sinh được dùng để duyệt hết các cấu hình có thể, trong một số bài toán thì 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 để chương trình được tối ưu hơn.

Tạm kết

Mình tạm dừng phần 1 ở đây, trong bài viết sau mình sẽ nói tiếp những yếu tố cần chăm sóc khác, những nguồn tài liệu và website mình hay dùng trong quy trình học. Các bạn đón xem nhé :))

Source: https://thomaygiat.com
Category : Kỹ Thuật Số