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

 

Giá trị của lần lặp lại sau đây là bao nhiêu.

T (n) = T (n / 4) + T (n / 2) + cn 2
T(1) = c
T (0) = 0

Trong đó c là hằng số dương

(A) O (n 3 )
(B) O (n 2 )
(C) O (n 2 Logn)
(D) O (nLogn)


Đáp án: (B)

Giải thích: Sau đây là cây đệ quy ban đầu cho quan hệ lặp lại đã cho .

           cn^2
         /      \
     T(n/4)     T(n/2)

Nếu chúng ta chia nhỏ thêm biểu thức T (n / 4) và T (n / 2), chúng ta sẽ nhận được cây đệ quy sau.

               cn^2
           /           \      
       c (n^2)/16       c(n^2)/4
      /      \          /     \
  T(n/16)     T(n/8)  T(n/8)    T(n/4) 

Chia nhỏ hơn nữa cho chúng ta theo dõi

                 cn^2
            /             \      
       c(n^2)/16           c(n^2)/4
       /      \            /      \
c(n^2)/256  c(n^2)/64  c(n^2)/64    c(n^2)/16
 /    \      /    \    /    \         /    \    
 

Để biết giá trị của T (n), chúng ta cần tính tổng các nút cây theo cấp độ. Nếu chúng ta tính tổng cây ở trên theo cấp, chúng ta nhận được chuỗi sau
T (n) = c (n ^ 2 + 5 (n ^ 2) / 16 + 25 (n ^ 2) / 256) +….
Dãy số trên là cấp tiến hình học với tỷ lệ 5/16
Để có giới hạn trên, chúng ta có thể tính tổng dãy số trên cho vô hạn. Chúng ta nhận được tổng là (n ^ 2) / (1 - 5/16) là O (n ^ 2)