Bài viết dựa trên cuốn sách "Cấu trúc dữ liệu và thuật toán" của thầy Nguyễn Đức Nghĩa - Đại học Bách Khoa Hà Nội.
" Nhân cái ngày mà người người nhà nhà ôn thi như thế này, sau khi đọc hết cuốn sách, mình nghĩ sao không thử viết 1 cái blog, vừa để chia sẻ mà lại ôn tập "
I. CÁC KHÁI NIỆM CƠ BẢN:
- Trong phần này chủ yếu nói đến các khái niệm về thuật toán và đánh giá.
- Đánh giá thuật toán dựa trên 2 tiêu chí cơ bản là :
- Tài nguyên máy tính
- Thời gian thực hiện (số phép toán thực hiện)
=> Sau đây chỉ nói về thời gian thực hiện:
- Có 3 loại thời gian tính:
- Thời gian tính tốt nhất (tiệm cận dưới) : loại này ít được quan tâm
- Thời gian tính trung bình
- Thời gian tính tồi nhất (tiệm cận trên) : BIG-O
=> Sau đây chỉ nói về Big-O:
Big O được hiểu là thời gian tính tồi nhất của một thuật toán (worst case) hay ý nghĩa hình học của nó được hiểu như là tiệm cận trên:
Định nghĩa: Hàm g(n) được gọi là big-o của f(n) khi mà tồn tại số nguyên dương c và no sao cho f(n) <= c*g(n) với mọi n => no.
Có hai quy tắc được quan tâm trong phần này là quy tắc nhân và quy tắc cộng: (cái này giống trong xác suất)
+ Quy tắc nhân : nếu có 2 vòng lặp lồng nhau vong lặp trong có O(g(n)), vòng lặp ngoài có O(h(n)) thì big-o của cả bài toán là O(g*h(n)).
+ Quy tắc cộng : nếu phần 1 có O(g(n)), phần 2 có O(h(n)), big-o của cả 2 phần là O(g+h(n)) thường sẽ chỉ lấy g(n)>h(n)?g(n):h(n).
II. THUẬT TOÁN ĐỆ QUY:
- Đệ quy được ứng dựng nhiều trong các thuật toán về cây, quay lui hay quy hoạch động... Ưu điểm của nó là dễ viết (hơn), dễ nhin, dễ hiểu. Nhược điểm là tốn bộ nhớ.
- Thuật toán đệ quy bao gồm 2 bước:
+ Neo đệ quy: đưa ra giá trị ban đầu của bài toán.
+ Gọi đệ quy: gọi đến các bài toán con nhỏ hơn.
+ Giải công thức truy hồi
Định lý thợ rút gọn : Giả sử xây dựng được hàm thời gian của bài toán
+ Gọi đệ quy: gọi đến các bài toán con nhỏ hơn.
- Các phương pháp đánh giá thuật toán đệ quy :
+ Giải công thức truy hồi
Định lý thợ rút gọn : Giả sử xây dựng được hàm thời gian của bài toán
T(n) = a*T(n/b) + c*n^k
xảy ra các trường hợp:
+ a > b^k : T(n) = O(n^logb(a))
+ a = b^b : T(n) = O((n^k)*log(n))
+ a < b^b : T(n) = O(n^k)
- Khử đệ quy: thường dùng nhất là stack, ngoài ra có thể dùng thêm biến phụ.
- Thuật toán đệ quy thường được chứng minh theo quy nạp
III. CÁC CẤU TRÚC DỮ LIỆU CƠ BẢN:
1. MẢNG :
4. HÀNG ĐỢI :
IV. CÂY :
- Mảng là cấu trúc quen thuộc từ lúc học nhập môn:
- Cấp phát mảng có 2 kiểu: cấp phát động và cấp phát tĩnh
- Mảng một chiều
- Cấp phát tĩnh : datatype arrayName[MAX_ELEMENTS];
- Cấp phát động : datatype *arrayName = (datatype*) malloc (MAX_ELEMENTS * sizeof ( datatype ));
- datatype arrayName = new datatype[MAX_ELEMENTS];
- Mảng 2 chiều:
- Cấp phát tĩnh : datatype arrayName[MAX_ROWS][MAX_COLS];
- C++:
int **a;
a = new int*[MAX_ROWS];
for(int i = 0; i < MAX_ROWS; i++)
a[i] = new int[MAX_COLS];
- Ta sẽ nói đến sự khác nhau giữa cấp phát động và cấp phát tĩnh :
- Ưu điểm nổi bật của mảng là có thể truy cập trực tiếp các phần tử.
- Các thao tác cơ bản:
- Thêm phân tử O(n)
- Xóa phần tử O(n)
- Truy cập phần tử O(1)
2. DANH SÁCH LIÊN KẾT :
- Danh sách liên kết là kiểu cấu trúc dữ liệu cực kỳ cơ bản, các cấu trúc khác sau này phức tạp hơn đều dựa trên danh sách liên kết.
- Danh sách liên kết là một kiểu con trỏ, dĩ nhiên được cấp phát động.
- Danh sách liên kết gồm nhiều loại:
- DSLK đơn
- DSLK đôi
- DSLK vòng
- DSLK đa ....
- Cấp phát phần tử : *arrayName = (datatype*) malloc (MAX_ELEMENTS * sizeof ( datatype ));
- Khai báo danh sách liên kết giống kiểu đệ quy
- Ưu điểm của DSLK là tiết kiệm bộ nhớ trong trường hợp, bộ nhớ dùng cho con trỏ nhỏ hơn nhiều so với dữ liệu, thuận tiện trong việc biểu diễn các mối quan hệ. Nhược điểm là không cho truy cập trực tiếp phần tử.
- Các thao tác cơ bản:
- Thêm, xóa O(1)
- Kiểm tra rỗng O(1)
- Truy cập phần tử O(n)
3. NGĂN XẾP :
- Ngăn xếp hay stack là cấu trúc dữ liệu hoạt động theo nguyên tắc First In Last Out - Vào trước ra sau.
- Ngăn xếp thường được biểu diễn bằng mảng hoặc danh sách liên kết.
- Ngăn xếp được ứng dụng trong khử đệ quy, kiểm tra thẻ HTML, chuyển biểu thức hậu tố sang trung tố.
- Các thao tác cơ bản:
- Thêm phần tử push()
- Lấy ra phần tử ở đầu pop()
- Lấy thông tin phần tử ở đầu top()
- Kiểm tra rỗng, đầy
4. HÀNG ĐỢI :
- Hàng đợi hay queue là cấu trúc dữ liệu hoạt động theo nguyên tắc First In First Out - Vào trước ra trước.
- Hàng đợi thường được biểu diễn bằng mảng hoặc danh sách liên kết.
- Hàng đợi được ứng dụng trong bài toán lập lịch, tổ chức công việc.
- Các thao tác cơ bản :
- Thêm phần tử : Enqueue()
- Lấy ra phần tử : Dequeue()
- Kiểm tra rỗng, đầy.
IV. CÂY :
- Cây là một cấu trúc dữ liệu bao gồm các nút, trong đó có 1 nút gốc.
- Cây được định nghĩa bằng đệ quy và các thuật toán trên cây cũng ưa thích đệ quy.
- Cây có thể biểu diễn bằng mảng, trên thực tế, người ta thường biểu diễn cây bằng danh sách liên kết.
- Duyêt cây : duyệt cây là thao tác cơ bản nhất trên cây,
- Duyệt trước (pre - order traversal) : nút cha được duyệt trước
- Duyệt giữa (in - order traversal): nút cha được duyệt giữa
- Duyệt sau (post - order traversal): nút cha được duyệt sau
- Một nút của cây có thể có một hoặc nhiều con, tuy nhiên, ta chỉ thường chỉ xét cây có nhiều nhất 2 cây con, được gọi cây nhị phân.
- Các thao tác với cây :
- Bổ sung nút
- Xóa nút
- Duyệt
- Tìm kiếm
- Tính chiều cao cây
Tham khảo code :
typedef int DataType;
typedef struct NodeType{
DataType Data;
NodeType *Leftchild;
NodeType *Rightchild;
};
NodeType *Root;
NodeType *fTmp;
int ld = 0;
int rd = 0;
NodeType *MakeNode(){
NodeType *Temp;
Temp=(NodeType*) malloc(sizeof(NodeType));
if(Temp==NULL) exit(1);
else{
Temp->Leftchild=NULL;
Temp->Rightchild=NULL;
}
return Temp;
}
NodeType *PreOrderFind(NodeType *fRoot,DataType ch){
if(fRoot->Data==ch) fTmp=fRoot;
else{
if(fRoot->Leftchild!=NULL) fTmp=PreOrderFind(fRoot->Leftchild,ch);
if(fRoot->Rightchild!=NULL) fTmp=PreOrderFind(fRoot->Rightchild,ch);
}
return fTmp;
}
void PreOrderTraversal(NodeType *fRoot){
printf(" %c ",fRoot->Data);
if(fRoot->Leftchild!=NULL) PreOrderTraversal(fRoot->Leftchild);
if(fRoot->Rightchild!=NULL) PreOrderTraversal(fRoot->Rightchild);
}
void InOrderTraversal(NodeType *fRoot){
if(fRoot->Leftchild!=NULL) InOrderTraversal(fRoot->Leftchild);
printf(" %c ",fRoot->Data);
if(fRoot->Rightchild!=NULL) InOrderTraversal(fRoot->Rightchild);
}
void PostOrderTraversal(NodeType *fRoot){
if(fRoot->Leftchild!=NULL) PostOrderTraversal(fRoot->Leftchild);
if(fRoot->Rightchild!=NULL) PostOrderTraversal(fRoot->Rightchild);
printf(" %c ",fRoot->Data);
}
void LeftChild(DataType ch1,DataType ch2){
NodeType *Tmp1;
NodeType *Tmp2;
Tmp2=MakeNode();
Tmp1=PreOrderFind(Root,ch1);
if(Tmp1==NULL) exit(1);
else{
Tmp1->Leftchild=Tmp2;
Tmp2->Data=ch2;
}
}
void MakeRoot(DataType ch){
Root=MakeNode();
Root->Data=ch;
}
void RightChild(DataType ch1,DataType ch2){
NodeType *Tmp1;
NodeType *Tmp2;
Tmp2=MakeNode();
Tmp1=PreOrderFind(Root,ch1);
if(Tmp1==NULL) exit(1);
else{
Tmp1->Rightchild=Tmp2;
Tmp2->Data=ch2;
}
}
int Height(NodeType *fRoot){
if(fRoot == NULL) return 0;
int ld = Height(fRoot->Leftchild);
int rd = Height(fRoot->Rightchild);
return ld > rd ? (ld+1):(rd+1);
}
int main(){
MakeRoot('a');
LeftChild('a','b');fTmp=NULL;
RightChild('a','c');fTmp=NULL;
LeftChild('b','d');fTmp=NULL;
RightChild('b','e');fTmp=NULL;
RightChild('d','j');fTmp=NULL;
LeftChild('d','h');fTmp=NULL;
LeftChild('e','k');fTmp=NULL;
RightChild('e','l');fTmp=NULL;
LeftChild('c','f');fTmp=NULL;
RightChild('c','g');fTmp=NULL;
printf("PreOrderTraversal: ");
PreOrderTraversal(Root);
printf("\nInOrderTraversal: ");
InOrderTraversal(Root);
printf("\nPostOrderTraversal: ");
PostOrderTraversal(Root);
printf("\nHeight: %d",Height(Root));
}
- Ứng dụng :
- Cây nhị phân biểu thức
- Cây quyết định
- Mã Huffman
V. CÁC THUẬT TOÁN SẮP XẾP :
- Bài toán sắp xếp hay sorting là bài toán tổ chức lại các họ dữ liệu theo thứ tự tăng hoặc giảm dần.
- Dữ liệu có thể là số, xâu, object ,...
- Thông thường khi học, ta hay sắp xếp mảng số nguyên. Trong thực tế, người ta thường sắp xếp các bản ghi có dung lượng lớn, khi đó, việc hoán đổi vị trí của chúng thường là khó khăn, thay vì đó, các bản ghi sẽ có 1 chỉ mục & ta sắp xếp trên đó.
- Các loại sắp xếp
- Sắp xếp trong : trong ở đây là trong bộ nhớ chính (RAM), sắp xếp 1 số lượng nhỏ phần tử.
- Sắp xếp ngoài : sắp xếp trên bộ nhớ ngoài
- Sắp xếp trên bộ nhớ trong thường tốn ít thời gian hơn bộ nhớ ngoài, nguyên nhân là do việc nạp dữ liệu từ bộ nhớ ngoài, việc sắp xếp trên bộ nhớ ngoài luôn quan tâm cần tối ưu số lần đọc dữ liệu từ bộ nhớ ngoài do tốc độ đọc bộ nhớ ngoài nhỏ hơn nhiều so với tốc độ đọc của RAM và tốc độ xử lý của CPU. Giải thuật ưu thích của sắp xêp ngoài là Merge Sort.
1. Các giải thuật sắp xếp cơ bản :
Bao gồm :
1.2 Sắp xếp nổi bọt :
1.3 Sắp xếp lựa chọn :
2. Các giải thuật sắp xếp nâng cao :
2.1 Sắp xếp trộn (merge sort) :
Thuật toán sắp xếp trộn dựa trên chia để trị, bao gồm các thao tác :
Bao gồm :
- Sắp xếp chèn (insert sort)
- Sắp xếp nổi bọt (bubble sort)
- Sắp xếp lựa chọn (selection sort)
=> Thời gian tính của các giải thuật này thường là O(n^2).
1.1 Sắp xếp chèn :
- Tại bước thứ k = 1,2,3...n đưa phần tử thứ k về đúng vị trí của nó, tức là vị trí cuối cùng của nó đứng sau khi đã sắp xếp.
- Kết quả là sau k bước, k phần tử được sắp thứ tự.
void insertionsort(int a[],int n){
int i;
for(int i = 1; i < n; i++){
if(a[i] < a[i-1]){
int j = i;
int x = a[j];
while(a[j-1] > x && j > 0){
a[j] = a[j-1];
j--;
}
a[j] = x;
}
}
}
1.2 Sắp xếp nổi bọt :
- Duyệt mảng theo 2 chiều ngược nhau, bắt đầu thuật toán, so sánh phần tử hiện tại với phần tử đứng sau nó và thực hiện đổi chỗ nếu chúng không đứng đúng thứ tự.
- Như vậy các phần tử lớn hơn dần dần được đẩy về cuối mảng, các phần tử nhỏ hơn dần dần được đưa về đầu mảng.
void bubblesort(int a[], int n){
for(int i = 0; i < n-1; i++)
for(int j = n-2; j > i; j--)
if(a[j] > a[j+1]){
int k = a[j];
a[j] = a[j+1];
a[j+1] = k;
}
}
1.3 Sắp xếp lựa chọn :
- Tại bước bước thứ k, đưa phần tử nhỏ thứ k vào vị trí thứ k.
- Như vậy, sau k bước, k phần tử đầu tiên sẽ được sắp đúng vị trí.
void selectionsort(int a[],int n){
int k;
for(int i = 0; i < n-1; i++){
k = i;
int min = a[i];
for(int j = i; j < n; j++){
if(a[j] < min){k = j; min = a[j];}
}
int m = a[k];
a[k] = a[i];
a[i] = m;
}
}
2. Các giải thuật sắp xếp nâng cao :
2.1 Sắp xếp trộn (merge sort) :
Thuật toán sắp xếp trộn dựa trên chia để trị, bao gồm các thao tác :
- Chia (Divide) : chia dãy gồm n phần tử ra thành 2 nửa, mỗi nửa có n/2 phần tử
- Trị (Conquer) :
- Sắp xếp mỗi dãy con một con đệ quy sử sụng sắp xếp trộn
- Khi dãy chỉ có 1 phần tử thì trả lại phần tử này
- Tổ hơp (Combine) : trộn 2 dãy con được sắp xếp để thu được dãy đã sắp xếp gồm tất cả phần tử của 2 dãy con.
=> Thời gian tính của merge sort là O(nlogn).
2.2 Sắp xếp nhanh (quick sort) :
Sắp xếp nhanh cũng dựa trên chia để trị, có thể mô tả như sau :
2.3.3 Cài đặt hàng đợi ưu tiên (Priority queue) :
Sắp xếp nhanh cũng dựa trên chia để trị, có thể mô tả như sau :
- Neo đệ quy : nếu dãy chỉ còn 1 phần tử thì dãy đã được sắp và trả lại luôn
- Chia :
- Chọn một phần tử trong dãy và gọi nó là phần tử chốt.
- Chia dãy đã cho thành 2 dãy con, dãy bên trái gồm những phần tử không lớn hơn chốt, dãy con phải gồm những phần tử không nhỏ hơn chốt. Thao tác này được gọi là thao tác phân đoạn (partition)
- Trị : Lặp lại một cách đệ quy thuật toán đối với 2 dãy con L và R.
- Tổ hợp : Dãy được sắp xếp là LpR.
=> Thời gian tính của quick sort thường phụ thuộc rất nhiều vào việc chọn phần tử nào là chốt, tuy nhiên trong phần lớn trường hợp là O(nlogn) và quick sort là thuật toán nhanh nhất.
2.3 Đống và sắp xếp vun đống (heap sort) :
2.3.1 Cấu trúc dữ liệu Heap :
- Heap là cây nhị phân gần hoàn chỉnh có 2 tính chất sau :
- Tính cấu trúc : tất cả mức cây đều là đầy, trừ mức cuối cùng được điền từ trái sang phải.
- Tính thứ tự.
- Hai dạng đống :
- Max-heap (phần tử ở gốc lớn nhất) (*)
- Min-heap (phần tử ở gốc nhỏ nhất)
- Đống được biểu diễn bằng mảng.
- Các thao tác với đống (max-heap)
- Khôi phục tính chất đống : Max-heapify : T(n) = O(logn)
- Xuất phát từ nút i nhỏ hơn con của nó (vi phạm điều kiện đống)
- Đổi chỗ với con lớn hơn
- Di chuyển xuống theo cây
- Tiếp tục cho đến khi nút i không còn con lớn hơn
- Xây đống : Build-max-heap : vì các phần tử từ n/2 +1 -> n là lá nên ta chỉ cần thực hiện max-heapify từ n/2 về 1. T(n) = O(n)
2.3.2 Sắp xếp vun đống :
- Tạo đống từ dãy đã cho
- Đổi chỗ phần tử đầu với phần tử cuối dãy
- Loại bỏ phần tử cuối bằng cách giảm kích thước mảng đi 1.
- Max-heapify với gốc mới
- Lặp lại cho đến khi heap còn 1 phần tử
=> Thời gian tính của heap sort là O(nlogn).
2.3.3 Cài đặt hàng đợi ưu tiên (Priority queue) :
- Cài đặt bằng max-heap (hoặc min-heap).
3.Các phương pháp sắp xếp đặc biệt :
3.1 Counting sort :
Input : n số nguyên trong khoảng [0,k] trong đó k là số nguyên và k = O(n).
- Ý tưởng :
- Với mỗi phần tử x của dãy đầu vào ta xác định hạng của nó như phần tử nhỏ hơn x.
- Duyệt mảng xếp hạng của các phần tử.
- Biết được phần tử có hạng r, ta sẽ đưa nó vào vị trí r+1.
3.2 Radix sort :
Input : n số nguyên, mỗi số có d chữ số.
- Ý tưởng : bước thứ k = 1;2;...;d sắp xếp theo chữ số thứ d.
3.3 Bucket sort :
Input : đầu vào gồm n số thực phân bố đều trong khoảng 0 -> 1 (các số có xác suất xuất hiện bằng nhau )
- Ý tưởng : chia đoạn 0 -> 1 ra làm n cụm
- Đưa mỗi phần tử aj vào đúng vị trí của nó i/n <= aj <= (i+1)/n
- Do các số là phân bố đều nên không có quá nhiều số đi vào 1 cụm.
- Nếu ta chèn chúng vào các cụm thì các cụm sẽ được sắp xếp đúng thứ tự.
VI. TÌM KIẾM :
Trong phần này chúng ta sẽ nói về các vấn đề chính là : các thuật toán tìm kiếm , cây nhị phân, bảng băm.
Trong phần này chúng ta sẽ nói về các vấn đề chính là : các thuật toán tìm kiếm , cây nhị phân, bảng băm.
- Có 2 thuật toán tìm kiếm phổ biến :
- Tìm kiếm tuần tự
- Tìm kiếm nhị phân
- Tìm kiếm tuần tự : Bắt đầu 1 mảng, với 1 khóa cần tìm. Ta duyệt mảng lần lượt các phần tử, so sánh chúng với khóa, nếu đúng trả về này. Thường thì chúng
YOUR_TEXT_HERE
Nhận xét
Đăng nhận xét