Xem mẫu
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í dụ: 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.)
20.2.2004 Ch. 2: Amortized Analysis 2
Sơ lược
° Ba phương pháp để xác định phí tổn khấu hao:
– Phương pháp gộp chung (the aggregate method) – Phương pháp kế toán (the accounting method) – Phương pháp thế năng (the potential method)
° Sẽ minh họa các phương pháp trên thông qua việc phân tích các cấu trúc dữ liệu:
– stack
– bộ đếm nhị phân có k bits – bảng động.
20.2.2004 Ch. 2: Amortized Analysis 3
Cấu trúc dữ liệu stack
° Các thao tác lên một stack S – PUSH(S, x)
– POP(S)
– MULTIPOP(S, k)
MULTIPOP(S, k)
1 while not STACKEMPTY(S) and k 0 2 do POP(S)
3 k k 1
20.2.2004 Ch. 2: Amortized Analysis 4
Bộ đếm nhị phân có k bit
° Bộ đếm nhị phân có kbit (kbit binary counter) – là một mảng A[0..k 1] của các bit
– có độ dài, length[A], là k
° Dùng bộ đếm để trữ một số nhị phân x: x = A[k 1] 2k 1 + … + A[0] 20
– Để cộng 1 vào trị đang có trong bộ đếm (modulo 2k), ta dùng thủ tục sau
INCREMENT(A) 1 i 0
2 while i < length[A] and A[i] = 1 3 do A[i] 0
4 i i + 1 5 if i < length[A]
6 then A[i] 1
20.2.2004 Ch. 2: Amortized Analysis 5
...
- tailieumienphi.vn
nguon tai.lieu . vn