CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Định lý tổng quát (Master theorem) tính độ phức tạp các thuật toán chia để trị

Posted by Trần Quốc Long on Tháng Một 9, 2009

Các thuật toán chia để trị thường chuyển bài toán lớn về các bài toán nhỏ rồi kết hợp lời giải các bài toán nhỏ để tạo ra kết quả của bài toán ban đầu. Để tính độ phức tạp của các thuật toán chia để trị, người ta thường sử dụng định lý tổng quát sau.

Định lý (Master theorem): Cho T(n) = a T(n/b) + f(n), ta có

  1. Nếu a f(n/b) = c f(n) với c > 1 thì T(n) = \Theta(n^{\log_b a}).
  2. Nếu a f(n/b)= c f(n) với c < 1 thì T(n)=\Theta(f(n)).
  3. Nếu a f(n/b) = f(n) thì T(n)=\Theta(f(n) \log_b n).

Nhận xét: Có thể hiểu là ta chia bài toán lớn ra thành a bài toán có kích thước n/b để giải rồi dùng f(n) phép tính để kết hợp lời giải các bài toán con lại.

Chứng minh:

Giả sử n=b^k (không mất tính tổng quát do ta có thể chọn k nhỏ nhất sao cho b^k\geq n), đồng thời giả sử ở trường hợp cơ sở n=1, ta có T(1) = f(1). Khai triển ra ta được.

T(n) = f(n) + aT(n/b) = f(n) + a f(n/b) + a^2T(n/b^2) = \ldots
\ldots = f(n) + a f(n/b) + a^2 f(n/b^2) + \ldots a^k f(n/b^k).

Trường hợp 1: Nếu a f(n/b) = c f(n) với c>1, ta có

f(n) = 1/c [af(n/b)]
af(n/b) = 1/c[ a^2 f(n/b^2)]
\ldots\ldots
a^{k-1} f(n/b^{k-1}) = 1/c [a^k f(n/b^k)]

Như vậy,  tổng trên bằng tổng dãy cấp số nhân (hệ số lũy tiến bằng c) có số hạng lớn nhất là a^k f(n/b^k). Như vậy, ta có

T(n) = \Theta (a^k f(n/b^k)) = \Theta (a^{\log_b n})=\Theta(n^{\log_b a})

Trường hợp 2: Nếu a f(n/b) = c f(n) với c<1, tương tự ta cũng có tổng dãy cấp số nhân với hệ số lũy tiến c<1 và số hạng lớn nhất là f(n). Như vậy, ta có

T(n) =\Theta(f(n))

Trường hợp 3: Nếu af(n/b) = f(n), các số hạng của tổng trên đều bằng nhau và bằng f(n), vậy

T(n) = (k+1)f(n) = \Theta(f(n) \log_b n)

Ví dụ:

  1. Thuật toán nhân số nguyên n-bit của Karatsuba-Ofman có độ phức tạp thuật toán T(n) = 3T(n/2) + O(n) = \Theta(n^{\log_2 3})= \Theta(n^{1,58}) theo trường hợp 1 (c=3/2) .
  2. Nếu T(n) = 3T(n/2)+n^2 thì T(n) = \Theta(n^2) theo trường hợp 2 (c=3/4).
  3. Thuật toán sắp xếp trộn (Merge Sort) có độ phức tạp thuật toán T(n) = 2T(n/2) + O(n) = \Theta(n \log_2 n) theo trường hợp 3.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: