Đánh giá độ phức tạp thuật toán – Phần II

Đánh giá độ phức tạp thuật toán – Phần II

(tiếp theo)
Đánh giá độ phức tạp thuật toán – Phần I

Khái niệm câu lệnh đặc trưng

Câu lệnh đặc trưng là câu lệnh được thực hiện thường xuyên ít nhất là cũng như bất kỳ câu lệnh nào trong thuật toán.
Nếu giả thiết thời gian thực hiện mỗi câu lệnh là bị chặn bởi hằng số thì thời gian tính của thuật toán sẽ cùng cỡ với số lần thực hiện câu lệnh đặc trưng. Do đó để đánh giá thời gian tính có thể đếm số lần thực hiện câu lệnh đặc trưng.

Sau đây, ta hãy cùng đánh giá độ phức tạp thuật toán thông qua một số ví dụ.

Sắp xếp nổi bọt

// algorithmist.com
void bubbleSort(int numbers[], int n) {
  int i, j, temp;
  for (i = (n - 1); i > 0; i--) {
    for (j = 1; j <= i; j++) {       
        if (numbers[j-1] > numbers[j]) {
        temp = numbers[j-1];
        numbers[j-1] = numbers[j];
        numbers[j] = temp;
      }
    }
  }
}

Ta chọn phép so sánh hai phần tử làm câu lệnh đặc trưng. Tại mỗi vòng lặp for thứ i, ta phải thực hiện phép so sánh i lần. Do đó tổng các phép so sánh là:

(n – 1) + (n – 2) + … + 2 + 1 = n(n-1)/2

Như vậy độ phức tạp của thuật toán là O()

Tìm kiếm nhị phân

Ý tưởng của thuật toán: Trong mỗi bước, so sánh phần tử cần tìm với phần tử nằm ở chính giữa danh sách. Nếu hai phần tử bằng nhau thì phép tìm kiếm thành công và thuật toán kết thúc. Nếu chúng không bằng nhau thì tùy vào phần tử nào lớn hơn, thuật toán lặp lại bước so sánh trên với nửa đầu hoặc nửa sau của danh sách.
Mã giả:

// wikipedia.org
Dữ liệu vào: danh sách tăng dần lưu trong mảng A từ phần tử thứ min đến phần tử thứ max, phần tử cần tìm x
Kết quả: thứ tự của x trong A nếu tìm thấy, nếu không trả về NOT_FOUND

while min < max
	mid ← ⌊(min+max)/2⌋
	if x > A[mid]
		min ← mid + 1
	else
		max ← mid

if min ≤ max and A[min] = x
	return min
else
	return NOT_FOUND

Ta chọn phép so sánh phần tử ở giữa danh sách với x làm câu lệnh đặc trưng. Dễ thấy sau mỗi bước số phần tử của danh sách giảm đi một nữa nên số lần thực hiện câu lệnh này sẽ là log(n) trong trường hợp tồi nhất. Từ đó ta có thể kết luận độ phức tạp của thuật toán này là O(log(n))

Giải thuật Fibonacci

Giải thuật này trả về số thứ n trong dãy số Fibonacci

int Fibo(int n) {
	if (n <= 1) return n;
	else
		return Fibo(n - 1) + Fibo(n - 2); (*)
}

Chọn phép cộng (*) làm câu lệnh đặc trưng. T(n) là số lần thực hiện câu lệnh này. Dễ thấy:

T(n) = 0 với n <= 1
T(n) = T(n-1) + T(n-2) + 1 với n > 1

Nhận xét: T(n) là hàm tăng theo số mũ. T(n) = O()
Suy ra: O() = O() + O() + O(1)
Bỏ qua O(1): = + = a + 1 ⇒ a = 1.618
Vậy T(n) =

Đị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 thì

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

int f(int n) {
	if (n > 1)
		return 8*f(n/2) + 2012; (*)
	return 0;
}

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

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

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

Khi trích dẫn bài viết từ tek.eten.vn, xin vui lòng ghi rõ nguồn. Chúng tôi sẽ rất cảm ơn bạn!