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)
إرسال تعليق