Merge Sort

Quy hoạch động

Trong ngành khoa học máy tính, quy hoạch động là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (overlapping subproblem) và cấu trúc con tối ưu (optimal substructure).

ĐỊNH LÝ THỢ RÚT GỌN – ÁP DỤNG VỚI MỘT SỐ THUẬT TOÁN ĐỆ QUY

Đối với các thuật toán đệ quy mà công thức đánh giá thuật toán có dạng:

 với a >= 1, b > 1, c > 0 là các hằng số

thì

• Nếu  thì 

• Nếu  thì 

• Nếu a >  thì 

1	int f(int n) {

2	if (n > 1)

3	return 8*f(n/2) + 2012; (*)

4

return 0;

5

}

T(n) = T(n/2) + 1 với n > 1

Ví dụ: Đánh giá độ phức tạp của thuật toán đệ quy sau:

Chọn (*) là câu lệnh đặc trưng. Dễ thấy

T(n) = 0 với n <= 1

Ở đây: a = 1, b = 2, c = 1, k = 0 ⇒ a = b^k ⇒ T(n) = O(logn)

Thuật toán sắp xếp chọn (Selection Sort)

1. Bài toán

Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.

Thuật toán Quick Sort

void quicksort(int a[10000] , int n , int low, int high) {

    /**< sap xep theo chieu tang dan  */

    int i = low ;

    int j = high ;

    int x = a[(low+high) /2] ;

    do {

        while (a[i] < x) i++ ;

        while (a[j]> x ) j -- ;

        if(i<=j) {

            int temp = a[i] ;

            a[i] = a[j] ;

            a[j] = temp ;

            i++ ;

            j-- ;

        }

    }

    while (i<= j) ;

    if( low<j) quicksort(a,n,low,j) ;

    if(i<high ) quicksort(a,n,i,high) ;

}