ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
TIỂU LUẬN MÔN HỌC
THIẾT KẾ VÀ PHÂN TÍCH THUẬT TOÁN
Đề tài:
PHÂN TÍCH KHẤU TRỪ
(AMORTIZED ANALYSIS)
Giáo viên hướng dẫn: Học viên thực hiện:
TS. Hoàng Quang Võ Thanh Minh
Nguyễn Quang
Hồ Văn Lâm
Phạm Vinh
Trần Thị Quế Vy

Nhóm 2-CHKHMT - Khóa 09-14
Huế, tháng 11/2014
2
MỤC LỤC
A. LỜI NÓI ĐẦU 4
B. NỘI DUNG 5
1.Giới thiệu một số bài toán 5
1.1 Bài toán 1: Các phép toán trên Stack 5
1.2 Bài toán 2: Tăng bộ đếm nhị phân 6
2.Các phương pháp của phân tích khấu trừ 7
2.1 Phương pháp kết tập: The Aggregate Method 8
2.2. Phương pháp kế toán: The accounting method 13
2.3 Phương pháp thế: The potential method 16
3.Bảng động (Dynamic tables) 20
3.1 Mở rộng bảng (Table expansion) 21
3.2 Thu gọn và mở rộng bảng 25
C. KẾT LUẬN 29

D. TÀI LIỆU THAM KHẢO 30
3
A. LỜI NÓI ĐẦU
Có nhiều phương pháp để đánh giá chi phí của một thuật toán, trong giới
hạn của tiểu luận môn học chúng tôi xin giới thiệu một phương pháp đó là
phương pháp phân tích khấu trừ để đánh giá chi phí của thuật toán.
Nội dung tiểu luận gồm có:
1. Giới thiệu một số bài toán
2. Các phương pháp của phân tích khấu trừ: trong phần này sẽ giới thiệu 3
phương pháp: phương pháp kết tập, phương pháp kế toán và phương pháp tiềm
năng. Với mỗi phương pháp sẽ chỉ ra đặc điểm và ứng dụng phương pháp vào
để xác định độ phức tạp của các bài toán được giới thiệu ở phần 1.
3. Bảng động: Giới thiệu một cách lưu trữ mới dựa vào bảng động, ở đó ta
có thê tùy ý thay đổi kích thước của bảng sao cho thích hợp với các mục dữ liệu
lưu trữ.
4
B. NỘI DUNG
1. Giới thiệu một số bài toán
1.1 Bài toán 1: Các phép toán trên Stack
Chúng ta đã biết hai phép toán cơ bản stack đó là PUSH và POP, mỗi phép
kéo theo dài O(1) thời gian, trong đó:
PUSH(S,x) bỏ đối tượng x vào stack S.
POP(S) lấy một đối tượng ra từ đầu stack S
Bởi từng phép toán này trong O(1) thời gian, ta hãy xem mức hao phí của
mỗi phép toán là 1. Do đó, tổng mức hao phí của một day n phép toán PUSH và
POP là n, và như vậy thời gian thực hiện thực tế cho n phép toán là Θ(n).
Có một tình huống xảy ra nếu ta bổ sung phép toán stack MULTIPOP(S,k)
để lấy k đối tượng ra khỏi stack S với k có thể lớn hơn số đối tượng trong stack
S Trong thuật toán MULTIPOP dưới đây, hàm STACK-EMPTY trả về TRUE
nếu không có đối tượng nào thực hiện nằm trên stack và bằng không là FALSE.

MULTIPOP(S, k)
1 while not STACK-EMPTY(S) and k
≠
0
2 do POP(S)
3 k
→
k - 1
Đâu là thời gian thực hiện của MULTIPOP(S,k) trên một stack gồm s đối
tượng? Thời gian thực hiện thực tế là tuyến tính trong số lượng phép toán POP
thực tế được thi hành, và như vậy nó đủ để phân tích MULTIPOP theo dạng các
mức hao phí trừu tượng là 1 cho PUSP và POP. Số lượng lần lặp lại của vòng
lặp While là số min(s,k) các đối tượng được kéo ra khỏi stack. Với mỗi lần lặp
lại vòng lặp, một lệnh gọi được thực hiện cho POP trong dòng 2. Như vậy, tổng
mức hao phí của MULTIPOP là min(s,k), và thời gian thực hiện thực tế là một
hàm tuyến tính của mức hao phí này.
Ví dụ: Thực hiện MULTIPOP trên một stack S, thọat đầu nêu trong (a). 4
đối tượng đầu được kéo ra bởi MULTIPOP(S,4) mà kết quả của nó được nêu
5
trong (b). Phép toán kế tiếp là MULTIPOP(S,6) sẽ xả trống stack-được nêu
trong (c)-bởi chỉ còn lại ít hơn 6 đối tượng.
Ta hãy phân tích một dãy n phép toán PUSH, POP và MULTIPOP trên một
stack trống từ đầu. Mức hao phí trường hợp xấu nhất của một phép toán
MULTIPOP trong dãy là O(n), bởi kích cỡ stack tối đa là n. Do đó, thời gian
trường hợp xấu nhất của bất kì phép toán stack nào là O(n) và như vậy một dãy
n phép toán sẽ có mức hao phí là O(n
2
), bởi ta có thể có O(n) phép toán
MULTIPOP, mỗi phép có mức hao phí là O(n). Mặc dù kiểu phân tích này là
đúng đắn, kết quả O(n

2
) có được nhờ xét mức hao phí trường hợp xấu nhất của
mỗi phép toán riêng lẻ, là không chặt.
1.2 Bài toán 2: Tăng bộ đếm nhị phân
Ta hãy xét bài toán thực thi một bộ đếm nhị phân k bít đếm lên từ 0. Ta
dùng một mảng A[0 k-1] bit, ở đó length[A] = k, là bộ đếm. Một số nhị phân x
được lưu trữ trong bộ đếm có k bit cấp thấp nhất của nó trong A[0] và bit cao
nhất trong A[k-1], sao cho . Thoạt đầu, x=0, như vậy A[i]=0 với
i=0,1,…k-1. Để cộng 1 (modulo 2
k
) vào giá trị trong bộ đếm ta dùng thủ tục dưới
đây:
6
Giá trị bộ đếm Tổng mức
hao phí
Hình 1.1(ở trang liền trước) Một đếm nhị phân 8-bit khi giá trị của nó đi từ
0 đến 16 theo một dãy 16 phép toán INCREMENT. Các bít lật để đựơc giá trị kế
tiếp được tô bóng. Mức hao phí thực hiện để lật các bít được nêu ở bên phải. Lưu
ý, tổng mức hao phí không bao giờ lớn hơn hai lần tổng phép toán
INCREMENT.
Thuật toán INCREMENT
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
Về cơ bản, thuật toán này giống như thuật toán đã được thực thị trong phần
cứng bằng một bộ đếm mang sang lược [ripple carry counter]. Hinh 1.1 cho biết
quá trình xảy ra với bộ đếm nhị phân khi nó được gia tăng 16 lần bắt đầu từ giá
trị ban đầu là 0 và kết thúc là giá trị 16. Bắt đầu mỗi lần lặp của vòng lặp While ở
dòng 2->4, ta hi vọng cộng thêm 1 vào vị trí i. Nếu A[i]=1 thì lật bit thành 0 ở vị
trí i và i =i+1 ở lần lặp tiếp theo của vòng lặp. Mặc khác, sau đó vòng lặp kết
thúc, nếu i<k, chúng ta biết rằng khi A[i]=0 thì lật 0 thành 1, được chỉ ra ở dòng
6. Chi phí cho mỗi phép toán INCREMENT là tuyến tính với số bit được lật.
Giống như trong ví dụ stack, một sự phân tích nhanh cho ra một cận tuy là
đúng nhưng không chặt. Một đợt thi hành INCREMENT sẽ mất một thời gian
Θ(k) trong trường hợp xấu nhất, ở đó mảng A chứa tất cả 1. Như vậy, một dãy n
phép toán INCREMETN trên một bộ đếm zero từ đầu sẽ mất một thời gian
O(nk) trong trường hợp xấu nhất.
2. Các phương pháp của phân tích khấu trừ
Trong phép phân tích khấu trừ, thời gian yêu cầu để thực hiện một dãy
các phép toán cấu trúc dữ liệu được tính bình quân trên tất cả các phép toán
7
thực hiện. Có thể dùng phép phân tích khấu trừ để chứng tỏ mức hao phí trung
bình của một phép toán là nhỏ, nếu như ta lấy bình quân trên một dãy các phép
toán, cho dù một phép toán đơn lẻ có thể là tốn kém. Phân tích khấu trừ khác
với phân tích trường hợp trung bình ở chỗ không có liên quan đến xác suất;
phân tích khấu trừ bảo đảm khả năng thực hiện trung bình của mỗi phép toán
trong trường hợp xấu nhất.
Trong phép phân tích khấu trừ có 3 phương pháp: phương pháp kết tập,

phương pháp kế toán và phương pháp tiềm năng
2.1 Phương pháp kết tập: The Aggregate Method
Trong phương pháp kết tập của phép phân tích khấu trừ, ta chứng tỏ với
tất cả n, một dãy n phép toán chiếm tổng cộng T(n) thời gian trường hợp xấu
nhất. Như vậy, trong trường hợp xấu nhất, chi phí trung bình hoặc chi phí khấu
trừ của mỗi phép toán là T(n)/n. Lưu ý, chi phí khấu trừ này áp dụng cho mỗi
phép toán, thậm chí khi có vài kiểu phép toán trong dãy.
Phương pháp kế toán và phương pháp thế, sẽ được giải thích sau trong
chương này, có thể gán các chi phí khấu trừ khác nhau cho các kiểu phép toán
khác nhau.
a. Ý tưởng của phương pháp:
Tính thời gian tổng cộng của tất cả các phép toán trong một dãy n phép
toán đó là T(n). Từ đó chi phí khấu trừ của mỗi phép toán trong trường hợp xấu
nhất là T(n)/ n.
b. Các ví dụ:
Để thể hiện ý tưởng của phương pháp vào các bài toán cụ thể ta xét 2 ví dụ
sau:
* Các phép toán trong ngăn xếp (Stack):
8
Trong ví dụ đầu tiên của chúng ta về phương pháp kết tập, ta phân tích
ngăn xếp đã được tăng cường một phép toán mới.
Chúng ta đã biết hai phép toán cơ bản stack đó là PUSH và POP, mỗi phép
kéo dài O(1) thời gian, trong đó:
PUSH(S,x) bỏ đối tượng x vào stack S.
POP(S) lấy một đối tượng ra từ đầu stack S và trả về đối tượng được kéo ra.
Bởi từng phép toán này trong O(1) thời gian, ta hãy xem chi phí của mỗi
phép toán là 1. Do đó, tổng chi phí của một dãy n phép toán PUSH và POP là n,
và như vậy thời gian thực hiện thực tế cho n phép toán là Θ(n).
Tình huống trở thành thú vị hơn nếu ta bổ sung phép toán stack
MULTIPOP(S,k) để lấy k đối tượng trên cùng ra khỏi stack S hoặc kéo ra tất cả

các đối tượng trong Stack nếu nó chứa ít hơn k đối tượng. Trong mã giả
MULTIPOP dưới đây, hàm STACK-EMPTY trả về TRUE nếu không có đối
tượng nào hiện nằm trên stack và ngược lại là FALSE.
MULTIPOP(S, k)
1 while not STACK-EMPTY(S) and k
≠
0
2 do POP(S)
3 k
→
k - 1
Đâu là thời gian thực hiện của MULTIPOP(S,k) trên một stack gồm s đối
tượng? Thời gian thực hiện thực tế là tuyến tính với số lượng phép toán POP
thực tế được thi hành, và như vậy nó đủ để phân tích MULTIPOP theo dạng các
chi phí trừu tượng là 1 cho PUSP và POP. Số lượng lần lặp lại của vòng lặp
While là số min(s,k) các đối tượng được kéo ra khỏi stack. Với mỗi lần lặp lại
vòng lặp, một lệnh gọi được thực hiện cho POP trong dòng 2. Như vậy, tổng chi
phí của MULTIPOP là min(s,k), và thời gian thực hiện thực tế là một hàm tuyến
tính của chi phí này.
Ví dụ: Thực hiện MULTIPOP trên một stack S, thọat đầu nêu trong (a). 4
đối tượng đầu được kéo ra bởi MULTIPOP(S,4) mà kết quả của nó được nêu
trong (b). Phép toán kế tiếp là MULTIPOP(S,7) sẽ xả trống stack-được nêu
trong (c)-bởi chỉ còn lại ít hơn 7 đối tượng.
9
Ta hãy phân tích một dãy n phép toán PUSH, POP và MULTIPOP trên một
stack trống từ đầu. Chi phí trường hợp xấu nhất của một phép toán MULTIPOP
trong dãy là O(n), bởi kích cỡ stack tối đa là n. Do đó, thời gian trường hợp xấu
nhất của bất kì phép toán stack nào là O(n) và như vậy một dãy n phép toán sẽ
có chi phí là O(n
2

), bởi ta có thể có n phép toán MULTIPOP, mỗi phép có chi
phí là O(n). Mặc dù kiểu phân tích này là đúng đắn, kết quả O(n
2
) có được nhờ
xét chi phí trường hợp xấu nhất của mỗi phép toán riêng lẻ, là không chặt.
Bây giờ ta dùng phương pháp của phân tích khấu trừ là phương pháp kết
tập với ý tưởng đã trình bày ở trên vào bài toán này ta sẽ thấy kết quả thú vị hơn.
Dùng phương pháp kết lập của phép phân tích khấu trừ, ta có thể được một
cận trên tốt hơn xem xét nguyên cả dãy n phép toán. Thực vậy mặc dù một phép
toán MULTIPOP đơn lẻ có thể tốn kém, bất kì dãy n phép toán PUSH, POP và
MULTIPOP nào trên một stack trống từ đầu có thể có chi phí tối đa O(n). Tại
sao? Mỗi đối tượng có thể được kéo ra tối đa một lần cho mỗi lần nó được bỏ
vào. Do đó, số lần mà POP có thể được gọi trên một stack không trống, kể cả
các lần gọi trong MULTIPOP, tối đa là số lượng các phép toán PUSH, mà các
phép toán này tối đa là n. Với bất kì giá trị nào của n, một dãy n phép toán
PUSH, POP và MULTIPOP bất kì đều chiếm một tổng O(n) thời gian. Chi phí
khấu trừ của một phép toán là số trung bình: O(n)/n=O(1).
Mặc dù ta vừa chứng minh chi phí trung bình và do đó thời gian thực hiện
của một phép toán stack là O(1), nhưng nó không liên quan đến biện luận xác
suất. Thực tế ta đã nêu một cận trong trường hợp xấu nhất của O(n) trên một dãy
10
n phép toán. Chia tổng chi phí này cho n đã cho ra chi phí trung bình của mỗi
phép toán hoặc chi phí khấu trừ.
* Phân tích bài toán 2:
Gia số bộ đếm nhị phân
Để lấy một ví dụ khác về phương pháp kết tập, ta hãy xét bài toán thực thi
một bộ đếm nhị phân k bít đếm lên từ 0. Ta dùng một mảng A[0 k-1] bit, ở đó
length[A] = k, làm bộ đếm. Một số nhị phân x được lưu trữ trong bộ đếm có bit
cấp thấp nhất của nó trong A[0] và bit cao nhất trong A[k-1], sao cho
[ ]

i
k
i
iAx 2
1
0
⋅=
∑
−
=
Thoạt đầu, x=0, như vậy A[i]=0 với i=0,1,…k-1. Để cộng 1 (modulo 2
k
)
vào giá trị trong bộ đếm ta dùng thủ tục dưới đây:
Hình 1.1 này biểu diễn một đếm nhị phân 8-bit khi giá trị của nó đi từ 0 đến
16 theo một dãy 16 phép toán INCREMENT. Các bít lật để đựơc giá trị kế tiếp
được tô bóng. Chi phí thực hiện để lật các bít được nêu ở bên phải. Lưu ý, tổng
chi phí không bao giờ lớn hơn hai lần tổng phép toán INCREMENT.
11
Tổng mức
chi phí
Giá trị bộ
đếm
Thuật toán INCREMENT
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
Về cơ bản, thuật toán này giống như thuật toán đã được thực thi trong phần
cứng bằng một bộ đếm mang sang lược [ripple carry counter]. Hình 1.1 cho biết
quá trình xảy ra với bộ đếm nhị phân khi nó được gia tăng 16 lần bắt đầu từ giá
trị ban đầu là 0 và kết thúc là giá trị 16. Tại đầu mỗi lần lặp của vòng lặp While ở
dòng 2->4, ta muốn cộng thêm 1 vào vị trí i. Nếu A[i]=1 thì lật bit thành 0 ở vị trí
i và cho ra một phép mang sang 1để được cộng vào vị trí i =i+1 ở lần lặp tiếp
theo của vòng lặp. Bằng không vòng lặp kết thúc, và như vậy nếu i<k, chúng ta
biết A[i]=0 , sao cho phép cộng 1 vào vị trí i thì lật 0 thành 1, được chỉ ra ở dòng
6. Chi phí của mỗi phép toán INCREMENT là tuyến tính với số bit được lật.
Giống như trong ví dụ stack, một sự phân tích nhanh cho ra một cận tuy là
đúng nhưng không chặt. Một đợt thi hành INCREMENT sẽ mất một thời gian
Θ(k) trong trường hợp xấu nhất, ở đó mảng A chứa tất cả 1. Như vậy, một dãy n
phép toán INCREMETN trên một bộ đếm zero từ đầu sẽ mất một thời gian
O(nk) trong trường hợp xấu nhất.
Bây giờ áp dụng phương pháp kết tập vào bài toán này ta có phân tích chặt
chẽ hơn để cho ra chi phí trường hợp xấu nhất là O(n) với một dãy n
INCREMENT bằng cách nhận xét rằng không phải tất cả các bit đều lật mỗi lần
INCREMENT được gọi. Như hình 1.1 đã nêu, A[0] lật một lần INCREMENT
được gọi. Bit cấp cao kế tiếp, A[1], chỉ lật mọi lần khác: một dãy n phép toán
INCREMETN trên một bộ đếm zero từ đầu sẽ khiến A[1] lật n/2 lần. Cũng
vậy, bit A[2] chỉ lật cứ 4 lần hoặc n/4 lần trong một dãy n INCREMENT. Nói

12
chung, với i=0,1,…, lg n , bit A[i] lật n/2
i
 lần trong một dãy n phép toán
INCREMENT trên một bộ đếm zero từ đầu. Với i>lg n , bit A[i] không hề lật
gì cả. Như vậy, tổng của các lần lật trong dãy là:
 
nn
n
i
i
n
i
i
2
2
1
2
0
lg
0
=<






∑∑
∞

==
Do đó, thời gian trường hợp xấu nhất cho một dãy n phép toán
INCREMENT trên một bộ đếm zero từ đầu là O(n), như vậy chi phí khấu trừ
của mỗi phép toán là O(n)/n=O(1).
Bài tập:
1. Nếu một phép toán MULTIPUSH được gộp vào tập hợp các phép toán ngăn
xếp, thì cận O (1) trên chi phí khấu trừ của các phép toán ngăn xếp tiếp tục đứng
vững không?
2. Chứng tỏ nếu một phép toán DECREMENT được gộp trong ví dụ bộ đếm
k- bit, n phép toán có thể có chi phí tối đa là Θ(nk) thời gian.
3. Một dãy n phép toán được thực hiện trên một cấu trúc dữ liệu, phép toán thứ
i có chi phí i nếu i là một lũy thừa chính xác của 2, mà bằng không là 1. Dùng
phương pháp kết tập của phân tích để xác định chi phí khấu trừ của mỗi phép
toán.
2.2. Phương pháp kế toán: The accounting method
Trong phương pháp kế toán của phân tích khấu trừ, ta gán các khoản tính
công khác biệt cho các phép toán khác nhau, với vài phép toán được tính công
nhiều hoặc ít hơn chi phí thực tế của chúng. Khoản mà ta tính công cho một
phép toán được gọi là mức hao phí khấu trừ của nó. Khi mức hao phí khấu trừ
của phép toán vượt quá chi phí thực tế của nó, sự khác biệt được gán cho các đối
tượng cụ thể trong cấu trúc dữ liệu dưới dạng khoản tín dụng.
Về sau khoản tín dụng có thể được dùng để giúp thanh toán cho những
phép toán có mức hao phí khấu trừ nhỏ hơn chi phí thực tế của chúng. Như vậy,
13
ta có thể xem mức hao phí khấu trừ của một phép toán dưới dạng đang được
tách giữa chi phí thực tế của nó với khoản tín dụng hoặc được ký gửi hoặc được
dùng hết. Điều này rất khác với phương pháp kết tập, ở đó tất cả các phép toán
có cùng mức hao phí khấu trừ.
Ta phải chọn mức hao phí khấu trừ của các phép toán thật cẩn thận. Nếu
muốn phân tích bằng mức hao phí khấu trừ để chứng tỏ mức hao phí trung bình

trong trường hợp xấu nhất của mỗi phép toán là nhỏ, tổng mức hao phí khấu trừ
của một dãy các phép toán phải là một cận trên trên tổng mức hao phí của dãy
đó. Hơn nữa, như trong phương pháp kết tập, mối quan hệ này phải áp dụng cho
tất cả các dãy phép toán. Như vậy, tổng khoản tín dụng kết hợp với cấu trúc dữ
liệu phải luôn là không âm, bởi nó biểu thị cho khoản mà tổng các mức hao phí
khấu trừ gánh chịu vượt quá tổng các chi phí thực tế gánh chịu. Nếu tổng khoản
tín dụng được phép trở thành âm (kết quả của việc tính công thiếu sớm cho các
phép toán với hứa hẹn hoàn trả khoản thanh toán về sau), thì tổng các mức hao
phí khấu trừ gánh chịu vào thời điểm đó sẽ nằm dưói tổng các chi phí thực tế
gánh chịu; với dãy các phép toán lên tới vào thời điểm đó, tổng mức hao phí
khấu trừ sẽ không phải là một cận trên trên tổng chi phí thực tế. Như vậy, ta
phải thận trong tổng khoản tín dụng trong cấu trức dữ liệu không bao giờ trở
thành âm.
Các phép toán ngăn xếp
Để minh họa phương pháp kế toán của phân tích khấu trừ, ta hãy trở lại ví
dụ ngăn xếp. Chắc bạn còn nhớ các chi phí thực tế của các phép toán là
PUSH 1,
POP 1,
MULTIPOP min(k, s),
Trong đó k là đối số cung cấp cho MULTIPOP và s là kích cỡ ngăn xếp khi
nó được gọi. Hãy gán các mức hao phí khấu trừ sau đây:
PUSH 2,
14
POP 0,
MULTIPOP 0,
Lưu ý, mức hao phí khấu trừ của MULTIPOP là hằng (0), trong khi đó chi
phí thực tế lại biến đổi. Ở đây, cả ba mức hao phí khấu trừ là O(1), mặc dù nói
chung các mức hao phí của các phép toán đang được xem xét có thể khác nhau
theo tiệm cận.
Giờ đây ta có thể thanh toán cho bất kỳ dãy phép toán ngăn xếp nào bằng

cách tính mức hao phí khấu trừ. Giả sử ta dùng một tờ đô la để biểu thị cho mỗi
đơn vị của mức hao phí. Ta bắt đầu một ngăn xếp rỗng. Hãy nhớ lại tương tự
của đoạn 10.1 giữa cấu trúc dữ liệu ngăn xếp và một ngăn xếp các đĩa trong một
quán ăn tự phục vụ. Khi đẩy một đĩa lên ngăn xếp, ta dùng 1 đô la để thanh toán
cho chi phí thực tế của lần đẩy và được để lại một khoản tín dụng 1 đô la (từ 2
đô la được tính công), mà ta đặt lên trên đĩa. Tại một điểm bất kỳ theo thời gian,
mọi đĩa trên xếp đền có một đô la khoản tín dụng nói trên.
Đô la được lưu trữ trên đĩa là khoản trả trước cho mức hao phí của tiến
trình kéo nó ra từ ngăn xếp. Khi ta thi hành một phép toán POP, ta không tính
công cho phép toán và thanh toán mức phí thực tế của nó bằng khoản tín dụng
lưu trữ trong ngăn xếp. Để kéo ra một đĩa, ta lấy đô la tín dụng ra khỏi đĩa và
dùng nó để thanh toán mức phí thật tế của phép toán. Như vậy, nhờ tính công
thêm một ít cho phép toán PUSH, ta không cần tính công cho phép toán POP.
Hơn nữa, ta cũng chẳng cần tính công cho các phép toán MULTIPOP. Để
kéo ra đĩa đầu tiên, ta lấy đô la của khoản tín dụng ra khỏi đĩa và dùng nó để
thanh toán chi phí thực tế của một phép toán POP. Để kéo ra một đĩa thứ hai, ta
lại có một đô la tín dụng trên đĩa để thanh toán cho phép toán POP, và cứ tiếp
tục như thế. Như vậy, ta luôn tính công trước ít nhất đủ để thanh toán cho các
phép toán MULTIPOP. Nói cách khác, do mỗi đĩa trên ngăn xếp có 1 đô la tín
dụng trên nó, và ngăn xếp luôn có một số đĩa không âm, ta bảo đảm khoản tín
dụng luôn không âm. Như vậy, với bất kỳ dãy nào n phép toán PUSH, POP và
15
MULTIPOP nào, tổng mức hao phí khấu trừ vẫn là một cận trên trên tổng chi
phí thực tế. Do tổng mức hao phí khấu trừ O(n), nên nó là tổng chi phí thực tế.
Bộ đếm tăng nhị phân
Để lấy một ví dụ khác về phương pháp kế toán, ta phân tích phép toán
INCREMENT trên một bộ đếm nhị phân bắt đầu tại zero. Như đã nhận xét ở
trên, thời gian thực hiện của phép toán này tỉ lệ với số lượng bit được lật, mà ta
sẽ dùng làm mức hao phí cho ví dụ này. Một lần nữa ta hãy dùng một đô la để
biễu thị cho mỗi đơn vị hao phí (tiến trình lật một bit trong ví dụ này).

Với phân tích khấu trừ, ta hãy tính công cho mức hao phí khấu trừ 2 đô la
để xác lập một bit là 1. Khi một bit được xác lập, ta dùng 1 đô la (từ 2 đô la
được tính công) để thanh toán cho xác lập thực tế của bit đó và ta đặt một đô la
kia trên bit đó làm khoản tín dụng. Tại bất kỳ điểm nào theo thời gian, mọi 1
trong bộ đếm đều có một đô la tín dụng trên nó, và như vậy ta chẳng cần tính
công gì cả để chỉnh lại một bit thành 0; ta chỉ cần thanh toán cho tiến trình chỉnh
lại bằng tờ đô la trên bit đó.
Giờ đây mức hao phí khấu trừ của INCREMENT có thể được xác định. Mức
hao phí của việc chỉnh lại các bit trong vòng lặp while được thanh toán bằng tờ
đô la trên các bit được chỉnh lại. Tối đa một bit được xác lập trong dòng 6 của
INCREMENT và do đó mức hao phí khấu trừ của phép toán INCREMENT tối
đa là 2 đô la. Số lượng 1 trong bộ đếm không bao giờ âm và như vậy khoản tín
dụng luôn không âm. Do đó, với n phép toán INCREMENT, tổng mức hao phí
khấu trừ là O(n), định cận tổng chi phí thực tế.
2.3 Phương pháp thế: The potential method
Thay vì biểu thị công được trả trước dưới dạng khoản tín dụng lưu trữ với
các đối tượng cụ thể trong cấu trúc dữ liệu, phương pháp thế của phân tích
khấu trừ biểu thị công được trả trước dưới dạng “năng lượng thế” hay đơn giản
là “thế”, có thể được giải phóng để dành cho các phép toán trong tương lai. Thế
16
được kết hợp với cấu trúc dữ liệu dưới dạng một toàn thể thay vì với các đối
tượng cụ thể trong cấu trúc dữ liệu.
Phương pháp làm việc như sau. Ta bắt đầu với một cấu trúc dữ liệu ban đầu
D
0
ở đó n phép toán được thực hiện. Với mỗi phép toán i = 1, 2,…, n, ta cho c
i
là
chi phí thực tế của phép toán thứ i và D
i

là cấu trúc dữ liệu kết quả sau khi áp
dụng phép toán thứ i lên cấu trúc dữ liệu D
i-1
. Một hàm thế Φ ánh xạ mỗi cấu
trúc dữ liệu D
i
theo một số thực Φ(D
i
), là thế kết hợp với cấu trúc dữ liệu D
i
. Chi
phí khấu trừ
i
c

của phép toán thứ i đối với hàm thế Φ được định nghĩa:
i
c

= c
i
+ Φ(D
i
) - Φ(D
i-1
) (2.3.1)
Do đó, chi phí khấu trừ của mỗi phép toán là chi phí thực tế của nó cộng
với mức gia tăng trong thế do phép toán. Theo phương trình (2.3.1), tổng chi phí
khấu trừ của n phép toán là:
∑ ∑∑

= =
−
=
Φ−Φ+=Φ−Φ+=
n
i
n
i
niiii
n
i
i
DDcDDcc
1 1
01
1
)()())()((
ˆ
(2.3.2)
Nếu ta có thể định nghĩa hàm thế Φ sao cho Φ(D
n
) ≥ Φ(D
0
), thì tổng chi phí
khấu trừ là một cận trên của tổng chi phí thực tế. Trong thực tế, không phải lúc
nào ta cũng biết có bao nhiêu phép toán có thể được thực hiện . Do đó, nếu ta
yêu cầu Φ(D
i
) ≥ Φ(D
0

) với mọi i, như trong phương pháp kế toán, thì ta đảm bảo
rằng có thuận lợi. Thường sẽ thuận lợi hơn nếu ta định nghĩa Φ(D
0
) = 0 và sau
đó chứng minh Φ(D
i
) ≥ 0 với mọi i. Nhận thấy, nếu hiệu Φ(D
i
)-Φ(D
i-1
) của phép
toán thứ i là dương, thì chi phí khấu trừ biểu thị cho một khoản tính công dư đối
với phép toán thứ i, và thế của cấu trúc dữ liệu sẽ gia tăng. Nếu hiệu thế là âm,
thì chi phí khấu trừ biểu thị cho một khoản tính công thiếu đối với phép toán thứ
i, và chi phí thực tế của phép toán được thanh toán bởi sự giảm trong thế.
Chi phí khấu trừ được định nghĩa bởi các phương trình (2.3.1 và 2.3.2) phụ
thuộc vào sự chọn lựa hàm thế Φ. Các hàm thế khác nhau có thể cho ra các chi
phí khấu trừ khác nhau nhưng vẫn là các cận trên của chi phí thực tế. Thường có
17
sự trả giá cho việc chọn một hàm thế; hàm thế tốt nhất tùy thuộc vào các cận
thời gian mong muốn.
Phân tích bài toán 1: Stack operations
Để minh họa phương pháp thế, một lần nữa ta quay lại với ví dụ về các
phép toán ngăn xếp PUSH, POP và MULTIPOP. Ta định nghĩa hàm thế Φ trên
một stack là số phần tử trong stack. Ta bắt đầu với stack rỗng D
0
, ta có Φ(D
0
)=0.
Vì số lượng các đối tượng trong stack không bao giờ âm nên: Φ(D

i
) ≥ 0 = Φ(D
0
)
với mọi i.
Do đó, tổng chi phí khấu trừ của n phép toán đối với Φ biểu thị cho một cận
trên của chi phí thực tế.
Giờ đây ta hãy tính toán các chi phí khấu trừ của các phép toán stack khác
nhau. Nếu phép toán thứ i trên một stack chứa s đối tượng là một phép toán
PUSH, thì hiệu thế là:
Φ(D
i
) - Φ(D
i-1
) = (s + 1) - s
= 1
Theo phương trình 2.3.1, chi phí khấu trừ của phép toán PUSH này

i
c
ˆ
= c
i


+ Φ(D
i
) - Φ (D
i-1
)

= 1 + 1
= 2
Giả sử rằng phép toán thứ i trên stack là MULTIPOP(S,k).
Đặt k’=min(k,s) đối tượng được lấy ra khỏi stack. Chi phí thực tế của phép
toán là k’ và hiệu thế là: Φ(D
i
) - Φ(D
i-1
) = k′.
Như vậy, chi phí khấu trừ của phép toán MULTIPOP là:
i
c
ˆ
= c
i

+ Φ(D
i
) - Φ(D
i-1
)
= k
’
– k
’
= 0
Tương tự, chi phí khấu trừ của một phép toán POP cũng là 0.
18
Chi phí khấu trừ của mỗi trong số ba phép toán là O(1), như vậy tổng chi
phí khấu trừ của một dãy n phép toán là O(n). Bởi ta đã chứng tỏ rằng Φ(D

i
) ≥
Φ(D
0
) với mọi i, nên tổng chi phí khấu trừ của n phép toán là một cận trên của
tổng chi phí thực tế. Do đó, chi phí trường hợp xấu nhất của n phép toán là O(n)
Phân tích bài toán 2:Increment
Lại xét tiến trình gia số một bộ đếm nhị phân. Lúc này, ta định nghĩa thế
của bộ đếm sau khi thực hiện phép toán INCREMENT thứ i là b
i
(b
i
chính là số
lượng bit 1 trong bộ đếm sau phép toán thứ i).
Ta hãy tính toán chi phí khấu trừ của một phép toán INCREMENT. Giả sử
phép toán INCREMENT thứ i chỉnh lại t
i
bit. Do đó, chi phí thực tế của phép
toán tối đa là t
i
+1, bởi ngoài việc chỉnh lại t
i
bit, nó xác lập tối đa một bit là 1.
Nếu b
i
=0 thì phép toán thứ i xác lập tất cả là k bit và vì thế
b
i-1

= t

i

= k.
Nếu b
i
>0 thì b
i

= b
i-1

- t
i

+ 1.
Trong cả hai trường hợp, b
i
≤ b
i-1
- t
i
+ 1 và hiệu thế là:
Φ(D
i
) - Φ(D
i-1
) ≤ (b
i-1

- t

i

+ 1) - b
i-1
= 1 - t
i
Vì thế, chi phí khấu trừ là:
i
c
ˆ
= c
i

+ Φ(D
i
) - Φ(D
i-1
)
≤ (t
i

+ 1) + (1 - t
i
) = 2
Nếu bộ đếm bắt đầu tại zero, thì
Φ(D
0
) = 0. Bởi Φ(D
i
) ≥ 0 với tất cả i, nên

tổng chi phí khấu trừ của một dãy n phép toán INCREMENT là một cận trên của
tổng chi phí thực tế và như vậy chi phí trường hợp xấu nhất của n phép toán
INCREMENT là O(n).
Phương pháp thế cho ta một cách dễ dàng để phân tích bộ đếm thậm chí khi
nó không bắt đầu tại zero. Thoạt đầu có b
0
bit 1 và sau n phép toán
INCREMENT sẽ có b
n
bit 1, trong đó 0 ≤ b
0
, b
n
≤ k. Ta có thể viết lại phương
trình (2.3.2) như sau:
∑ ∑
= =
Φ+Φ−=
n
i
n
i
nii
DDcc
1 1
0
)()(
ˆ
(17.4)
Ta có

i
c
ˆ
≤ 2 với 1 ≤ i ≤ n. Vì Φ(D
0
) = b
0
và Φ(D
n
) = b
n
nên tổng chi phí thực tế
19
của n phép toán INCREMENT sẽ là:
∑ ∑
= =
+−≤
n
i
n
i
ni
bbc
1 1
0
2
= 2n - b
n
+ b
0

Đặc biệt, chú ý do b
0
≤ k, nếu ta thực hiện ít nhất n = Ω(k)
phép toán
INCREMENT, tổng chi phí thực tế là O(n) bất kể bộ đếm chứa giá trị ban đầu
nào.
3. Bảng động
(
Dynamic tables)
Trong vài ứng dụng, ta không biết trước bao nhiêu đối tượng sẽ được lưu
trữ trong một bảng. Ta có thể phân bổ không gian cho một bảng, để rồi về sau
phát hiện không đủ. Như vậy, bảng phải được phân bổ lại với kích thước lớn hơn
và tất cả các đối tượng được lưu trữ trong bảng ban đầu phải được chép vào
bảng mới, lớn hơn. Cũng vậy, nếu nhiều đối tượng đã được xoá ra khỏi bảng ta
cũng nên phân bổ lại theo kích thước nhỏ hơn. Trong đoạn này, ta nghiên cứu
bài toán năng động mở rộng và rút gọn một bảng. Dùng phép phân tích khấu trừ,
ta sẽ chứng tỏ mức hao phí khấu trừ của một phép của phép chèn và phép xoá
chỉ là O(1), cho dù mức hao phí thực tế của phép toán là lớn khi nó ứng tác một
phép mở rộng hay phép rút gọn. Hơn nữa, ta sẽ xem làm thế nào để bảo đảm
không gian còn rảnh trong một bảng động không bao giờ vượt quá một số bất
biến của tổng không gian.
Ta mặc nhận rằng bảng động hỗ trợ các phép toán TABLE-INSERT và
TABLE-DELETE. TABLE-INSERT chèn vào bảng một mục choán một khe
đơn lẻ, nghĩa là, một khoảng không gian cho một mục. Cũng vậy, ta có thể xem
TABLE-DELETE như gỡ bỏ một mục ra khỏi bảng, đồng thời giải phóng một
khe. Các chi tiết của phương pháp cấu trúc dữ liệu được dùng để tổ chức bảng là
không quan trọng, ta có thể dùng một stack, một đống hoặc một bảng băm.
Cũng có thể dùng một mảng hoặc tập hợp các mảng để thực thi kho lưu trữ đối
tượng.
Để tiện dụng, ta dùng một khái niệm đã giới thiệu trong phần phân bảng

băm. Ta định nghĩa
hệ số tải

α
(T) của một bảng không trống T là số lượng các
mục lưu trữ trong bảng chia cho kích cỡ (số lượng các khe) của bảng. Ta gán
cho bảng trống (bảng kh
ông có mục nào) kích cỡ 0 và ta định nghĩa hệ số tải của
nó là 1. Nếu hệ số tải của một bảng động được định cận dưới theo một hằng, thì
không gian còn rảnh trong bảng sẽ không bao giờ nhiều hơn một phân số bất
20
biến của tổng lượng không gian.
Để bắt đầu, ta phân tích một bảng động ở đó ta chỉ thực hiện các phép chèn.
Sau đó, ta xét trường hợp chung hơn ở đó cả phép chèn lẫn phép xoá đều được
phép.
3.1
Mở rộng bảng (
Table expansion)
Mặc định rằng kho lưu trữ cho một bảng được phận bổ dưới dạng một
mảng các khe. Một bảng đầy khi tất cả các khe đã được dùng hoặc tương
đương, khi hệ số tải của nó là 1. Trong vài môi trường phần mềm, nếu cố chèn
một mục vào một bảng đã đầy, ta không có cách nào khác ngoài việc phải bỏ
ngang cùng với một lỗi. Tuy nhiên, ta mặc nhận môi trường phần mềm, cũng
như nhiều môi trường hiện đại, sẽ cung cấp một hệ quản lý bộ nhớ có thể phân
bổ và giải phóng các khối lưu trữ theo yêu cầu. Như vậy, khi một mục được
chèn vào một bảng đầy, ta có thể
mở rộng
bảng bằng cách phân bổ một bảng
mới có nhiều khe hơn bảng cũ rồi chép các mục từ bảng cũ vào bảng mới.
Một phép phỏng đoán chung đó là phân bổ một bảng mới có số khe nhiều

gấp hai lần so với bảng cũ. Nếu chỉ thực hiện các phép chèn, hệ số tải của một
bảng luôn ít nhất là ½, và như vậy lượng không gian lãng phí không bao giờ
vượt quá nửa tổng không gian trong bảng.
Trong mã giả dưới đây, ta mặc nhận rằng T là một đối tượng biểu thị
bảng. Trường
table
[T] chứa một biến con trỏ đến khối lưu trữ biểu thị cho
bảng. Trường
num
[T] chứa số lượng các mục trong bảng và trường
size
[T] là
tổng của các khe trong bảng. Thoạt đầu, bảng là trống:
num
[T]=
size
[T]=0.
TABLE-INSERT (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]
21
10 insert x into table[T]
11 num[T]
→
num[T] + 1
Lưu ý, ta có hai thủ tục “chèn” ở đây: chính thủ tục TABLE-INSERT và
phép chèn cơ bản vào một bảng trong các dòng 6 và 10. Ta có thể phân tích
thời gian thực hiện của TABLE-INSERT theo dạng số lượng phép chèn cơ bản
bằng cách gán một mức hao phí 1 cho từng phép chèn cơ bản. Ta mặc nhận
rằng thời gian thực hiện thực tế của TABLE-INSERTA là tuyến tính theo thời
gian để chèn các mục riêng lẻ, sao cho phần việc chung để phân bổ một bảng
ban đầu trong dòng 2 là bất biến và phần việc chung để phân bổ và giải phóng
kho lưu trữ trong các dòng 5 và 7 bị chi phối bởi mức hao phí chuyển giao các
mục trong dòng 6. Ta gọi sự kiện ở đó mệnh đề Then trong các dòng 5-9 được
thi hành là một phép mở rộng (expension).
Ta hãy phân tích một dãy n phép toán TABLE-INSERT trên một bảng
trống từ đầu. Đâu là mức hao phí c
i
của phép toán thứ i? Nếu có chỗ trong bảng
hiện hành (hoặc nếu đây là phép toán đầu tiên) thì c
i
=1, bởi ta chỉ cần thực
hiện một phép chèn cơ bản trong dòng 10. Tuy nhiện, nếu bảng hiện hành đầy
và một phép mở rộng xảy ra, thì c
i
= i: mức hao phí là 1 cho phép chèn cơ bản
trong dòng 10 cộng với i-1 cho các mục phải được chép từ bảng cũ sang bảng

mới trong dòng 6. Nếu n phép toán được thực hiện, mức hao phí trường hợp
xấu nhất của một phép toán là O(n), dẫn đến một cận trên O(n
2
) trên tổng thời
gian thực hiện của n phép toán.
Cận này không chặt, bởi mức hao phí của tiến trình mở rộng bảng thường
không phát sinh trong quá trình diễn biến của n phép toán TABLE-INSERT. Cụ
thể, phép toán thứ i chỉ đưa đến một phép mở rộng là một luỹ thừa chính xác của
2. Mức hao phí khấu trừ của một phép toán thực tế là O(1), như ta có thể chứng
tỏ bằng phương pháp kết tập. Mức hao phí của phép toán thứ i là
Do đó, tổng mức hao phí của n phép toán TABLE-INSERT là
22



=
1
i
c
i
nếu i -1 =2
j
( j nguyên)
Trong các trường hợp khác
 
nnn
nc
n
j
j

n
i
i
32
2
)1lg(
01
=+<
+=
∑∑
−
==
Bởi có tối đa n phép toán có mức hao phí là 1 và các mức hao phí của các
phép toán còn lại sẽ hình thành một seri cấp số nhân. Bởi tổng mức hao phí của
n phép toán TABLE-INSERT là 3n nên mức hao phí khấu trừ của một phép toán
đơn lẻ là 3.
Nếu dùng phương pháp kế toán, ta có thể cảm nhận được tại sao mức hao
phí khấu trừ của một phép toán TABLE-INSERT phải là 3. Theo trực giác, mỗi
mục thanh toán cho 3 phép chèn cơ bản: phép chính nó trong bảng hiện hành,
dời chính nó khi bảng mở rộng và dời một mục khác đã được dời một lần khi
bảng mở rộng. Ví dụ, giả sử kích cỡ của bảng là m liền sau một phép mở rộng.
Như vậy, số lượng các mục trong bảng là m/2 và bảng không chứa khoản tín
dụng nào. Ta tính công 3 đôla cho mỗi phép chèn. Phép chèn cơ bản xảy ra tức
thời có mức hao phí là 1 đôla. Một đôla khác được đặt trên mục đã chèn dưới
dạng một khoản tín dụng. Đôla thứ 3 được đặt trên một trong m/2 mục sẵn có
trong bảng dưới dạng một khoản tín dụng. Việc điền đầy bảng yêu cầu m/2 -1
phép chèn bổ sung và như vậy cho đến lúc đó bảng chứa m mục và đầy, mỗi
mục có một đôla để thanh toán cho phép chèn lại của nó trong khi mở rộng.
Phương pháp thế cũng có thể được dùng để phân tích một dãy n phép toán
TABLE-INSERT và ta sẽ dùng nó trong

3.2
để thiết một phép toán TABLE-
INSERT cũng có mức hao phí khấu trừ O(1). Để bắt đầu, ta định nghĩa một hàm
thế
Φ bằng 0 liền sau một phép mở rộng nhưng tạo nên kích cỡ bảng vào lúc
bảng đầy sao cho phép mở rộng kế tiếp có thể được thanh toán bởi phép thế.
Hàm

(17.5)
là một khả năng. Liền sau một phép mở rộng, ta có
num
[T]=
size
[T]/2 và như vậy
Φ(T)=0, như mong muốn. Liền trước một phép mở rộng, ta có
num
[T]=
size
[T]
và như vậy
Φ(T) = num[T] , như mong muốn. Giá trị bảng đầu của thế là 0, do
đó bảng luôn ít nhất đầy phân nửa, nên num[T] ≥ size[T]/2 , hàm ý Φ(T) luôn
không âm. Như vậy, tổng các mức hao phí khấu trừ của n phép toán TABLE-
INSERT là một cận trên trên tổng các mức hao phí thực tế.
23
Để phân tích mức hao phí khấu trừ của phép toán TABLE-INSERT thứ i,
ta có num
i
thể hiện số lượng các mục được lưu trữ trong bảng sau phép toán thứ
i, size

i
thể hiện tổng kích cỡ của bảng sau phép toán thứ i và Φ
i
thể hiện thế sau
phép toán thứ i. Thoạt đầu, ta có num
0
=0, size
0
=0 và Φ
0
=
0
Nếu phép toán TABLE-INSERT thứ i không ứng tác một phép mở rộng
thì size
i
= size
i-1
và mức hao phí khấu trừ của phép toán là
= 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.
Nếu phép toán thứ i ứng tác một phép mở rộng, thì size
i

= 2 · size
i-1
và
size
i-1


= num
i-1
= num
i
– 1 và mức hao phí khấu trừ của phép toán là
= 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

- 1)) - (2(num
i

- 1) - (num
i

- 1))
= num
i

+ 2 - (num
i

- 1)
= 3.
Hình 3.1 chấm vẽ các giá trị num
i
, size
i
và Φ
i
đối lại i. Lưu ý, cách thức mà thế
xây dựng để thanh toán cho phép mở rộng của bảng.
Hiệu ứng của một dãy n phép toán TABLE-INSERT trên số num
i
của các

mục trong bảng, số size
i
của các khe trong bảng và thế Φ
i

= 2·num
i

- size
i
, tất cả
đều được tính sau phép toán thứ i. Đường kẻ mảnh chỉ num
i
, đường kẻ dày chỉ
size
i
và đường gạch cách chỉ Φ
i
. Lưu ý, liền trước mọt phép mở rộng, thế đã
24
hình thành theo số lượng các mục trong bảng và do đó nó có thể thanh toán cho
việc dời tất cả các mục sang bảng mới. Sau đó, thế tụt xuống đến 0 nhưng lập
tức nó được tăng lên 2 khi chèn mục do phép mở rộng gây ra.
3.2 Thu gọn và mở rộng bảng
Để thực thi một phép toán TABLE-INSERT ta chỉ cần gỡ bỏ mục đã chỉ
định ra khỏi bảng. Tuy nhiên, thông thường ta nên rút gọn bảng khi hệ số tải của
bảng trở thành quá nhỏ, sao cho không gian lãng phí không quá cao. Phép rút
gọn bảng tương tự như phép mở rộng bảng: khi số lượng các mục trong bảng tụt
xuống quá thấp, ta phân bổ một bảng mới, nhỏ hơn rồi chép các mục từ bảng cũ
sang bảng mới. Sau đó, có thể giải phóng kho lưu trữ cho bảng cũ bằng cách trả

nó về hệ thống quản lý bộ nhớ. Về ý tưởng, ta muốn bảo toàn hai tính chất:
 Hệ số tải của bảng động được chặn dưới bởi một hằng
 Mức hao phí khấu trừ của mỗi phép toán là O(1)
Ta mặc nhận mức hao phí có thể được tính theo dạng các phép chèn và phép
xoá cơ bản.
Một chiến lược tự nhiện để mở rộng và rút gọn đó là nhân đôi kích cỡ
bảng khi một mục được chèn vào một bảng đầy và chia đôi kích cỡ khi một phép
xoá khiến bảng chỉ còn đầy ít hơn một nửa. Chiến lược này bảo đảm hệ số tải
của bảng không bao giờ tụt xuống dưới ½, nhưng đáng tiếc, nó có thể khiến mức
hao phí khấu trừ của một phép toán trở nên khá lớn. Xét trường hợp dưới đây.
Ta thực hiện n phép toán trên một bảng T, ở đó n là một luỹ thừa chính xác của
2, n/2 phép toán đầu tiên là các phép chèn, mà theo phân tích trên đây của chúng
ta có tổng mức hao phí là Φ(n). Ở cuối dãy phép chèn này num[T] = size[T] =
n/2. Với n/2 phép toán thứ hai, ta thực hiện dãy dưới đây:
I, D, D, I, I, D, D, I, I, ,
Ở đó I thay cho phép chèn và D thay cho một phép xoá. Phép chèn đầu
tiên khiến một phép mở rộng của bảng theo kích cỡ n. Hai phép xoá sau khiên
một phép rút gọn bảng trở về kích cỡ n/2. Hai phép chèn sau đó khiến một phép
mở rộng khác… Mức hao phí của mỗi phép mở rộng và phép rút gọn là Θ(n) và
có Θ(n) của chúng. Như vậy, tổng mức hao phí của n phép toán là Θ(n
2
) và mức
ho khấu trừ của một phép toán là Θ(n).
25