ĐỊ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) ;

}