Phân tích thuật toán (Recurrences) | Bài 2

 

Độ phức tạp thời gian trong trường hợp xấu nhất khi thực hiện sau bài toán tổng tập hợp con là gì.

// Returns true if there is a subset of set[] with sun equal to given sum bool isSubsetSum(int set[], int n, int sum) {    // Base Cases    if (sum == 0)      return true;    if (n == 0 && sum != 0)      return false;        // If last element is greater than sum, then ignore it    if (set[n-1] > sum)      return isSubsetSum(set, n-1, sum);        /* else, check if sum can be obtained by any of the following       (a) including the last element       (b) excluding the last element   */    return isSubsetSum(set, n-1, sum) ||            isSubsetSum(set, n-1, sum-set[n-1]); }

(A) O (n * 2 ^ n)
(B) O (n ^ 2)
(C) O (n ^ 2 * 2 ^ n)
(D) O (2 ^ n)


Đáp án: (D)

Giải thích: Sau đây là sự lặp lại cho việc triển khai đã cho của bài toán tổng tập hợp con

T (n) = 2T (n-1) + C1
T (0) = C1

Trong đó C1 và C2 là một số hằng số cụ thể của máy.

Nghiệm của sự tái diễn là O (2 ^ n)

Chúng ta có thể thấy nó với sự trợ giúp của phương pháp cây tái phát

           C1
       /       \
    T(n-1)     T(n-1) 


                    C1
                /       \
              C1 C1
           /     \        /    \
      T(n-2)  T(n-2)   T(n-2)  T(n-2)

                    C1
                /       \
              C1 C1
           /     \        /    \
          C1 C1 C1 C1
        /   \   /  \    /  \   /  \

       
Nếu chúng ta tổng hợp các cấp độ cây ở trên theo cấp độ, chúng ta nhận được chuỗi sau
T (n) = C1 + 2C1 + 4C1 + 8C1 + ...
Dãy số trên là cấp số nhân Hình học và sẽ có n số hạng trong đó.
Vậy T (n) = O (2 ^ n)