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