Bài giảng Giải thuật - Chương 3: Phân tích khấu hao
° Phân tích khấu hao
° Gọi T(n) là thời gian cần thiết để thực thi một chuỗi n thao tác lên một cấu trúc dữ liệu.
– Ví du: thực thi một chuỗi PUSH, POP, MULTIPOP lên một stack.
° Phân tích khấu hao (amortized analysis):
– Thời gian thực thi một chuỗi các thao tác được lấy trung bình trên số các thao tác đã thực thi,
T(n)/n ,
được gọi là phí tổn khấu hao.
(Đây chỉ là một trong các định nghĩa của phí tổn khấu hao, các định nghĩa khác sẽ được trình bày trong các phần sau.)
Bạn đang xem trước 20 trang tài liệu Bài giảng Giải thuật - Chương 3: Phân tích khấu hao, để xem tài liệu hoàn chỉnh bạn click vào nút TẢI VỀ ở trên
.2004 26 Ch. 2: Amortized Analysis Phương pháp thế năng: phân tích bộ đếm nhị phân dài k bits Dùng phương pháp thế năng để xác định chi phí khấu hao của mỗi thao tác (tiếp) Tính phí tổn khấu hao của một thao tác I NCREMENT I NCREMENT thứ i resets t i bits và sets nhiều lắm là 1 bit. Vậy phí tổn thực sự của I NCREMENT thứ i nhiều lắm là t i + 1. Hiệu thế là ( D i ) ( D i 1 ) = b i b i 1 , mà b i b i 1 t i + 1. Vậy ( D i ) ( D i 1 ) 1 t i . Phí tổn khấu hao là c ^ i = c i + ( D i ) ( D i 1 ) t i + 1 + 1 t i = 2 . 12.9.2004 27 Ch. 2: Amortized Analysis Phương pháp thế năng: phân tích bộ đếm nhị phân dài k bits Trị của bộ đếm bắt đầu bằng 0, nên ( D 0 ) = 0, do đó ( D i ) ( D 0 ). Vậy chi phí khấu hao tổng cộng là chận trên cho chi phí thực sự tổng cộng. Phí tổn trong trường hợp xấu nhất của n thao tác là O ( n ). 12.9.2004 28 Ch. 2: Amortized Analysis Bảng động Trong một số ứng dụng, dùng một “bảng” để trữ các đối tượng mà không biết trước bao nhiêu đối tượng sẽ được trữ. Do đó khi bảng hiện thời không có đủ chổ cho các đối tượng mới, cần một bảng mới với kích thước lớn hơn. khi bảng hiện thời dư nhiều chổ trống do xoá nhiều đối tượng, cần một bảng mới với kích thước nhỏ hơn. Các thao tác lên một bảng T ABLE -I NSERT : chèn một item vào bảng T ABLE -D ELETE : xóa một item khỏi bảng. 12.9.2004 29 Ch. 2: Amortized Analysis Hệ số sử dụng của một bảng Định nghĩa hệ số sử dụng (load factor) của một bảng T (không trống) là ( T ): ( T ) = số khe (slots) có chứa đối tượng trong bảng chia cho số khe của bảng. Bài toán : Xác định chiến lược nới rộng và thu nho û bảng sao cho hệ số sử dụng của bảng cao được chận dưới bởi một hằng số chi phí khấu hao của T ABLE -I NSERT và T ABLE -D ELETE là O (1). 12.9.2004 30 Ch. 2: Amortized Analysis Chiến lược mở rộng một bảng Chiến lược khi nào thì nới rộng một bảng được diễn tả trong giải thuật sau. T ABLE -I NSERT ( T , x ) 1 if size [ T ] = 0 2 then allocate table [ T ] with 1 slot 3 size [ T ] 1 4 if num [ T ] = size [ T ] 5 then allocate new-table with 2 size [ T ] slots 6 insert all items in table [ T ] into new-table 7 free table [ T ] 8 table [ T ] new-table 9 size [ T ] 2 size [ T ] 10 insert x into table [ T ] 11 num [ T ] num [ T ] 1 12.9.2004 31 Ch. 2: Amortized Analysis Chiến lược mở rộng một bảng (tiếp) T ABLE -I NSERT thực thi T ABLE -I NSERT ... 12.9.2004 32 Ch. 2: Amortized Analysis Phân tích một chuỗi T ABLE -I NSERT Giả sử: Thời gian thực thi của T ABLE -I NSERT tỉ lệ với thời gian chèn từng item (“chèn sơ đẳng”) vào bảng ở dòng 6 và 10. Chi phí của một chèn sơ đẳng là 1. Sẽ phân tích chi phí của một chuỗi gồm n I NSERT lên một bảng động dùng lần lượt các phương pháp gộp chung kế toán thế năng. 12.9.2004 33 Ch. 2: Amortized Analysis Phân tích chuỗi T ABLE -I NSERT bằng phương pháp gộp chung Dùng phương pháp gộp chung để xác định chi phí khấu hao của I NSERT Chi phí c i của thao tác thứ i là i nếu i 1 = 2 j là 1 trong các trường hợp còn lại. Chi phí của n thao tác T ABLE -I NSERT là n tổng các 2 j từ j = 0 đến lg n n 2 n = 3 n . Vậy chi phí khấu hao của I NSERT là 3 n n = 3. 12.9.2004 34 Ch. 2: Amortized Analysis Phân tích chuỗi T ABLE -I NSERT bằng phương pháp kế toán Dùng phương pháp kế toán để xác định chi phí khấu hao của T ABLE -I NSERT Chi phí khấu hao của T ABLE -I NSERT là 3 . Trả như sau: 1 đồng để trả cho chi phí thực sự cho riêng nó 1 đồng để trả trước cho chính nó một khi nó được di chuyển lúc bảng nới rộng 1 đồng để trả trước cho một item khác trong bảng mà không còn tiền trả trước (vì đã di chuyển). 12.9.2004 35 Ch. 2: Amortized Analysis Phân tích chuỗi T ABLE -I NSERT bằng phương pháp thế năng Dùng phương pháp thế năng để phân tích một chuỗi gồm n thao tác I NSERT lên một bảng Định nghĩa thế năng là ( T ) = 2 num [ T ] size [ T ]. Nhận xét Ngay sau khi nới rộng (dòng 9 của T ABLE -I NSERT thực thi xong) num [ T ] = size [ T ] 2 ( T ) = 0 . Ngay trước khi nới rộng num [ T ] = size [ T ] ( T ) = num [ T ]. (0) = 0, ( T ) 0. Vì vậy tổng của các chi phí khấu hao của n thao tác T ABLE -I NSERT là một chận trên lên tổng của các chi phí thực sự. 12.9.2004 36 Ch. 2: Amortized Analysis Phân tích chuỗi T ABLE -I NSERT bằng phương pháp thế năng (tiếp) Xác định chi phí khấu hao của mỗi thao tác Giả sử thao tác thứ i không gây nới rộng. Ta có size i = size i 1 . Chi phí khấu hao của thao tác là c ^ i = c i i i 1 = 1 (2 num i size i ) (2 num i 1 size i 1 ) = 1 (2 num i size i ) (2( num i 1) size i )) = 3 . 12.9.2004 37 Ch. 2: Amortized Analysis Phân tích chuỗi T ABLE -I NSERT bằng phương pháp thế năng Xác định chi phí khấu hao của mỗi thao tác (tiếp) Giả sử thao tác thứ i gây nới rộng. Ta có size i / 2 = size i 1 = num i 1 . Chi phí khấu hao của thao tác là c ^ i = c i i i 1 = num i (2 num i size i ) (2 num i 1 size i 1 ) = num i (2 num i (2 num i 2)) (2( num i 1)( num i 1)) = num i 2 ( num i 1) = 3 . 12.9.2004 38 Ch. 2: Amortized Analysis Xóa một item khỏi bảng Thêm thao tác “ Xóa một item khỏi bảng ”: T ABLE -D ELETE . Hệ số sử dụng của bảng có thể trở nên quá nhỏ. Nhắc lại định nghĩa của hệ số sử dụng là ( T ) = num [ T ] / size [ T ]. Ta muốn giử hệ số sử dụng cao, tức là nó được chận dưới bằng một hằng số. chi phí bù trừ của một thao tác lên bảng được chận trên bằng một hằng số. Giả sử chi phí được đo bằng số lần chèn hay xoá item sơ đẳng. 12.9.2004 39 Ch. 2: Amortized Analysis Chiến lược nới rộng và thu nhỏ bảng Một chiến lược tự nhiên cho nới rộng và thu nhỏ bảng là Gấp đôi bảng khi chèn một item vào một bảng đã đầy. Giảm nửa bảng khi xóa một item khỏi một bảng chỉ đầy nửa bảng. Phân tích Chiến lược trên bảo đảm ( T ) 1/2. 12.9.2004 40 Ch. 2: Amortized Analysis Chiến lược nới rộng và thu nhỏ bảng Phân tích (tiếp) Tuy nhiên phí tổn khấu hao của mỗi thao tác có thể rất lớn: Lấy n có dạng 2 m Xét một chuỗi n thao tác (I là một insert và D là một delete) I I ( n /2 lần), kế đó là I D D I I D D I I ( n /2 lần). Chuỗi n thao tác này có phí tổn là ( n 2 ), do đó phí tổn khấu hao của mỗi thao tác là ( n ). 12.9.2004 41 Ch. 2: Amortized Analysis Chiến lược nới rộng và thu nhỏ bảng (tiếp) Cải tiến chiến lược trên bằng cách cho phép hệ số sử dụng có thể trở nên nhỏ hơn 1/2: Nếu ( T ) = 1, thì thao tác T ABLE -I NSERT sẽ gấp đôi bảng. Nếu ( T ) = 1/4, thì thao tác T ABLE -D ELETE sẽ giảm nửa bảng. 12.9.2004 42 Ch. 2: Amortized Analysis Chiến lược thu nhỏ một bảng (tiếp) bảng mới = 1/2 bảng cũ (T) = 1/4 thực thi T ABLE -D ELETE 12.9.2004 43 Ch. 2: Amortized Analysis Phương pháp thế năng Dùng phương pháp thế năng để phân tích một chuỗi gồm n thao tác T ABLE -I NSERT và T ABLE -D ELETE lên một bảng. Định nghĩa thế năng trên một bảng là ( T ) = 2 num [ T ] size [ T ] nếu ( T ) 1/2 = size [ T ] / 2 num [ T ] nếu ( T ) 1/2 12.9.2004 44 Ch. 2: Amortized Analysis Phương pháp thế năng (tiếp) Nhận xét : (bảng trống) = 0, và ( T ) 0 Nếu hệ số sử dụng là 1/2 thì ( T ) = 0. Nếu hệ số sử dụng là 1 thì ( T ) = num [ T ]. Đủ để trả phí tổn một khi có nới rộng bảng do chèn một item. Hệ số sử dụng là 1/4 thì ( T ) = num [ T ]. Đủ để trả phí tổn một khi có thu nhỏ bảng do xoá một item. 12.9.2004 45 Ch. 2: Amortized Analysis Phân tích một chuỗi các T ABLE -I NSERT và T ABLE -D ELETE Xác định chi phí khấu hao của mỗi thao tác Nếu thao tác thứ i là T ABLE -I NSERT , ta phân biệt các trường hợp: i 1 1/2 theo Section 18.4.1, thì c ^ i nhiều lắm là 3. i 1 1/2, ta phân biệt 2 trường hợp: trường hợp i 1/2 c ^ i = c i i i 1 = 0 . trường hợp i 1/2 c ^ i = c i i i 1 = 3 . Vậy chi phí khấu hao của thao tác T ABLE -I NSERT nhiều lắm là 3. 12.9.2004 46 Ch. 2: Amortized Analysis Phân tích một chuỗi các T ABLE -I NSERT và T ABLE -D ELETE Xác định chi phí khấu hao của mỗi thao tác (tiếp) Nếu thao tác thứ i là T ABLE -D ELETE , thì num i = num i 1 1, ta phân biệt các trường hợp: i 1 1/2. Có hai trường hợp con không gây thu nhỏ: size i = size i 1 c ^ i = c i i i 1 = 2 . gây thu nhỏ: c i = num i 1, size i / 2 = size i 1 / 4 = num i 1 c ^ i = c i i i 1 = 1 . i 1 1/2. Bài tập 18.4-3. Vậy chi phí khấu hao của T ABLE -D ELETE được chận trên bởi một hằng số. 12.9.2004 47 Ch. 2: Amortized Analysis Phân tích một chuỗi các T ABLE -I NSERT và T ABLE -D ELETE (tiếp) Kết luận : Vì chi phí khấu hao của mỗi thao tác T ABLE -I NSERT và T ABLE -D ELETE được chận trên bởi một hằng số, nên thời gian chạy cho một chuổi bất kỳ gồm n thao tác lên một bảng động là O ( n ). 12.9.2004 48 Ch. 2: Amortized Analysis
File đính kèm:
bai_giang_giai_thuat_chuong_3_phan_tich_khau_hao.ppt
