Cơ Sở Dữ Liệu Và Giải Thuật (Data Structure And Algorithms), Cấu Trúc Dữ Liệu Và Giải Thuật Trong C/C++

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

Bạn đang xem: Cơ sở dữ liệu và giải thuật

Trong bài viết này, mình sẽ tổng hợp những kiến thức cơ phiên bản cùng các kinh nghiệm của chính mình để giúp chúng ta đi đúng hướng và cảm thấy sự độc đáo của môn học này. Tất yếu xung xung quanh ta vẫn có nhiều cao thủ, việc trình làng các kỹ năng khó sẽ khiến cho mọi bạn bị ngợp đề xuất trong phạm vi nội dung bài viết này, bản thân sẽ reviews các vụ việc cơ bản (ít duy nhất là trong những bài kiểm soát trên trường). Hãy thuộc tham khảo nội dung bài viết dưới đây:

Chuẩn bị phần nhiều gì nhằm học thuật toán?

Đầu tiên, nhằm học được cấu trúc tài liệu và giải thuật (Từ giờ đến cuối bài viết mình sẽ điện thoại tư vấn tắt là thuật toán), các bạn cần phải có kĩ năng tự học cao. Phải có công dụng tìm tìm tốt. Số đông mọi lắp thêm cơ bản đều có trên google, trong khuôn khổ nội dung bài viết này bản thân sẽ gửi ra các vấn đề quan lại trọng, để chúng ta follow theo từ khóa đó, tìm kiếm cho chính mình một nền tảng vững vàng chắc.

Tiếp theo, các bạn cần chọn cho chính mình một ngôn từ lập trình. Theo bản thân thì C/C++ là ngôn từ nên được sử dụng khi học thuật toán vì:

Các kiểu tài liệu trong ngữ điệu C/C++ được khái niệm rõ ràng, tất cả kiểu truyền tham chiếu và tham trị tương đối hay.Tốc độ thực hiện nhanh.Có những sách, tài liệu xem thêm trên internet về cấu trúc dữ liệu và lời giải được viết bởi C/C++.

Tuy nhiên, nếu muốn hoặc có nền tảng những ngôn ngữ không giống (java, python,...) thì mọi fan cũng có thể sử dụng nhằm học được vì theo công thức sau:

Cấu trúc dữ liệu + lời giải = Chương trình

Việc viết một chương trình, giải một việc được phối hợp bởi 2 yếu hèn tố, lựa lựa chọn một cấu trúc dữ liệu phù hợp, tiếp nối tìm ra phương hướng kết hợp mọi thứ bằng giải thuật để rất có thể giải được bài toán. Bởi vì đó bạn có thể lựa chọn ngôn từ yêu thích với bắt đầu.

Các sự việc cần quan tâm

Trong phần này bản thân sẽ nói đến 7 vụ việc sau:

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

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

3. Các cách thức sinh

4. Đệ quy, cù lui

5. Kết cấu dữ liệu stack, queue, dequeue

6. Quy hoạch động

7. Đồ thị.

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

Khái niệm độ tinh vi thuật toán có thể hiểu dễ dàng và đơn giản là độ nhanh hay chậm chạp của thuật toán. Chữ O là cam kết hiệu được áp dụng cho độ tinh vi thuật toán. Những loại độ phức tạp thuật toán cơ bạn dạng có thể kể tới là:

Trong đó, n là bộc lộ kích thước đầu vào.

Lưu ý rằng nếu chúng ta sử dụng 2 vòng lặp cùng cung cấp thì kích cỡ sẽ là 2*n, tuy nhiên độ phức tạp thuật toán biểu diễn vẫn luôn là O(n) vì mình chỉ lấy xê dịch thôi.

Và nếu bạn của người sử dụng nói là 2 vòng lặp lồng nhau thì độ phức hợp sẽ là O(n^2) thì bọn họ đôi khi yêu cầu xem xét kỹ hơn thuật toán. Như ví dụ như sau:

int i = 0;int n = 1000;while (i nếu như không để ý thì có thể sẽ nhầm hàm này là O(N^2), nhưng thực tiễn độ tinh vi của nó là O(n). Chính vì nếu như i

2. Thu xếp và search kiếm nhị phân

a. Sắp xếp

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

Bubble sortSelection sortInsertion sortQuick sortHeap sort...

Xem thêm: 120 Câu Trích Dẫn Hay Trong Phim Việt, Trung, Hàn, 120 Câu Trích Hay Trong Phim Ý Tưởng

Ngoài ra còn không hề ít thuật toán thu xếp khác nữa, tùy vào đk môn học tập trên trường yêu mong gì thì mình học tập theo. Còn theo khiếp nghiệm của mình thì để triển khai 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 giỏi dùng luôn hàm sort trong thư viện( trong C++ là hàm sort trong thư viện algorithm bao gồm độ tinh vi ~ O(nlog(n))).

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

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

Ý tưởng thiết yếu của tìm kiếm có thể biểu diễn đơn giản bằng một việc như sau:

Có n bạn được xếp thành một hàng theo đồ vật tự độ cao tăng dần. Thầy giáo chú ý vào danh sách học sinh mà không tồn tại tên, chỉ tất cả chiều cao, cho nên vì thế cần tìm chúng ta có chiều cao là X trong hàng.

Bình thường thì phương pháp làm đơn giản và dễ dàng nhất là duyệt từ đầu hàng đến cuối hàng một cách lần lượt, khi đó chắc chắn sẽ tìm được bạn có chiều cao là X đó (độ phức tạp thuật toán sẽ là O(n)). Có một cách nhanh hơn để giải bài toán này, đó là ta sẽ nhìn vào người ở giữa dãy, nếu bạn đó có chiều cao bằng X thì ta sẽ tìm được luôn, còn nếu ko thì ta sẽ biết chắc chắn người đó sẽ đứng ở nửa nào trong 2 nửa còn lại của hàng, qua đó lặp lại phương pháp bên trên đến lúc tìm ra bạn đó, đây chính là ý tưởng chính của thuật toán tìm kiếm nhị phân với độ phức tạp chỉ còn O(nlog(n)).

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

Có thể bạn chưa biết, gần như tất cả các bài toán đều có thể giải bằng cách duyệt trâu từng trường hợp. Vày đó các phương pháp sinh là không thể thiếu khi học thuật toán. Có 4 hướng pháp sinh mà các bạn nhất định phải học:

Sinh nhị phânSinh hoán vịSinh tổ hợpSinh chỉnh hợp

Các bạn có thể tìm hiểu các thuật toán bên trên và submit trong trang sau nhé:

https://www.spoj.com/PTIT/problems/basic/

4. Đệ quy, con quay lui

Nói 1-1 giản thì đệ quy là hàm gọi lại chính nó, biểu diễn đối tượng được định nghĩa quy nạp theo các đối tượng nhỏ đồng dạng với nó. Sau đây là một số ví dụ của hàm sử dụng vòng lặp bình thường và hàm đệ quy:

int giaithua(int n) {int res=1;for (int i = 1; i Bây giờ hãy cùng mình nhìn qua một số cách viết hàm tính a^b ( với a khác 0). Tất nhiên với các bài toán giới hạn lớn thì a^b sẽ rất lớn, vì đó mình sẽ lấy phần dư cho mod nhé.

// dpt O(n)long long cal_pow(int a, int b, int mod) long long res=1;for (int i = 1; i > 1, mod);Qua đó các bạn có thể thấy các hàm đệ quy rất thú vị. Các phương pháp sinh ở trên, ngoài cách code chay sinh từng cấu hình thì cũng có thể sử dụng đệ quy để viết một cách gọn gàng hơn. Thuật toán con quay lui cũng dựa trên tứ tưởng của hàm đệ quy như trên, suy đến cùng các thuật toán sinh được dùng để duyệt hết các cấu hình có thể, trong một số bài toán thì có thể sử dụng nhánh cận, cài cắm các đoạn xử lý loại bỏ các trường hợp không cần thiết để chương trình được tối ưu hơn.

Tạm kết

Mình tạm dừng phần 1 ở đây, vào bài viết sau mình sẽ nói tiếp các vấn đề cần thân thương khác, các nguồn tài liệu và trang web mình hay dùng vào quá trình học. Các bạn đón coi nhé :))