Bài giảng Phân tích thiết kế giải thuật - Chương 2: Phân tích khấu hao (Amortized Analysis)
Phaân Tích Khaáu Hao
Phaân tích khaáu hao
° Goïi T(n) laø thôøi gian caàn thieát ñeå thöïc thi moät chuoãi n thao taùc leân
moät caáu truùc döõ lieäu.
– Ví duï: thöïc thi moät chuoãi PUSH, POP, MULTIPOP leân moät stack.
° Phaân tích khaáu hao (amortized analysis):
– Thôøi gian thöïc thi moät chuoãi caùc thao taùc ñöôïc laáy trung bình
treân soá caùc thao taùc ñaõ thöïc thi,
T(n)/n ,
ñöôïc goïi laø phí toån khaáu hao.
(Ñaây chæ laø moät trong caùc ñònh nghóa cuûa phí toån khaáu hao, caùc ñònh
nghóa khaùc seõ ñöôïc trình baøy trong caùc phaàn sau.)
12.9.2004
Ch. 2: Amortized Analysis
2
Sô löôïc
° Ba phöông phaùp ñeå xaùc ñònh phí toån khaáu hao:
– goäp chung (the aggregate method)
– keá toaùn (the accounting method)
– theá naêng (the potential method)
° Seõ minh hoïa caùc phöông phaùp treân thoâng qua vieäc phaân tích caùc caáu
truùc döõ lieäu:
– stack
– boä ñeám nhò phaân daøi k bits
– baûng ñoäng.
12.9.2004
Ch. 2: Amortized Analysis
3
Caáu truùc döõ lieäu stack
° Caùc thao taùc leân moät stack S
– PUSH(S, x)
– POP(S)
– MULTIPOP(S, k)
MULTIPOP(S, k)
1 while not STACK-EMPTY(S) and k 0
2
3
do POP(S)
k k − 1
12.9.2004
Ch. 2: Amortized Analysis
4
Caáu truùc döõ lieäu stack (tieáp)
° Minh hoïa thao taùc MULTIPOP
top → 23
33
4
MULTIPOP(S, 4)
45
4
78
----
MULTIPOP(S, 7)
top → 4
78
----
----
12.9.2004
Ch. 2: Amortized Analysis
5
Boä ñeám nhò phaân daøi k bit
° Boä ñeám nhò phaân daøi k-bit (k-bit binary counter)
– laø moät maûng A[0..k − 1] cuûa caùc bit
– coù ñoä daøi, length[A], laø k.
12.9.2004
Ch. 2: Amortized Analysis
6
Boä ñeám nhò phaân daøi k bit (tieáp)
° Duøng boä ñeám ñeå tröõ moät soá nhò phaân x:
x = A[k − 1]2k − 1 + … + A[0]20
– INCREMENT: coäng 1 vaøo trò ñang coù trong boä ñeám (modulo 2k)
INCREMENT(A)
1
0
1
1
0
1
0
0
– Thuû tuïc INCREMENT
INCREMENT(A)
1 i 0
2 while i < length[A] and A[i] = 1
3
4
do A[i] 0
i i + 1
5 if i < length[A]
6
then A[i] 1
12.9.2004
Ch. 2: Amortized Analysis
7
Phaân tích moät stack
° Baøi toaùn: xaùc ñònh thôøi gian chaïy cuûa moät chuoãi n thao taùc leân moät
stack (ban ñaàu stack laø troáng).
Giaûi baèng phaân tích “thoâ sô”:
—
Phí toån trong tröôøng hôïp xaáu nhaát cuûa MULTIPOP laø O(n). Vaäy
phí toån trong tröôøng hôïp xaáu nhaát cuûa moät thao taùc baát kyø leân
stack laø O(n).
—
Do ñoù phí toån cuûa moät chuoãi n thao taùc laø O(n2).
° Nhaän xeùt: Chaän O(n2) tìm ñöôïc laø quaù thoâ.
° Tìm chaän treân toát hôn!
– Duøng phaân tích khaáu hao.
12.9.2004
Ch. 2: Amortized Analysis
8
Phöông phaùp goäp chung
° Ñònh nghóa: Trong phöông phaùp goäp chung (aggregate) cuûa phaân
tích khaáu hao, chuùng ta goäp chung thôøi gian maø moät chuoãi n thao taùc
caàn trong tröôøng hôïp xaáu nhaát (worst case) thaønh T(n).
– Chi phí khaáu hao (amortized cost) cuûa moãi thao taùc ñöôïc ñònh
nghóa laø chi phí trung bình cho moãi thao taùc, töùc laø T(n)/n.
12.9.2004
Ch. 2: Amortized Analysis
9
Phöông phaùp goäp chung: phaân tích stack
° Phaân tích moät chuoãi n thao taùc leân moät stack S (maø khi baét ñaàu thì
stack laø troáng), chuoãi goàm caùc loaïi thao taùc
– PUSH(S, x)
– POP(S)
– MULTIPOP(S, k)
° Duøng phöông phaùp goäp chung ñeå xaùc ñònh chi phí khaáu hao cuûa moãi
thao taùc
– Moãi ñoái töôïng coù theå ñöôïc popped toái ña laø moät laàn sau khi noù
ñöôïc pushed. Soá PUSH toái ña laø n, vaäy soá laàn POP ñöôïc goïi, keå
caû töø MULTIPOP, laø n.
– Vaäy phí toån cuûa chuoãi n thao taùc PUSH, POP, vaø MULTIPOP laø
O(n).
– Do ñoù phí toån khaáu hao cuûa moãi thao taùc laø O(n)/n = O(1).
12.9.2004
Ch. 2: Amortized Analysis
10
Phöông phaùp goäp chung: phaân tích boä ñeám nhò phaân
° Phaân tích moät chuoãi goàm n thao taùc INCREMENT leân moät boä ñeám nhò
phaân coù chieàu daøi k bit
° Duøng phöông phaùp goäp chung ñeå xaùc ñònh chi phí khaáu hao cuûa moãi
thao taùc.
– Nhaän xeùt (giaû söû trò ban ñaàu cuûa boä ñeám laø 0)
bit A[0] flips n
laàn
bit A[1]
bit A[2]
...
n/2
n/4
Toång quaùt:
bit A[i] flips n/2i laàn, i = 0,…, lg n
bit A[i] khoâng flips neáu i > lg n .
– Tính ñöôïc toång cuûa n/2i töø i = 0 ñeán lg n laø 2n .
12.9.2004
Ch. 2: Amortized Analysis
11
Phöông phaùp goäp chung: phaân tích boä ñeám nhò phaân
° Duøng phöông phaùp goäp chung ñeå xaùc ñònh chi phí khaáu hao cuûa moãi
thao taùc (tieáp)
– Vaäy thôøi gian xaáu nhaát cho moät chuoãi n thao taùc INCREMENT leân
moät boä ñeám (maø trò ban ñaàu laø 0) laø O(n).
Thôøi gian khaáu hao cho moãi thao taùc laø O(n)/n = O(1).
° Nhaän xeùt: Phaân tích thoâ sô
– Khi moïi bit cuûa boä ñeám laø 1, thao taùc INCREMENT coù theå caàn
ñeán thôøi gian xaáu nhaát laø (k).
– Do ñoù moät chuoãi n thao taùc INCREMENT caàn thôøi gian xaáu nhaát laø
nO(k) = O(nk).
12.9.2004
Ch. 2: Amortized Analysis
12
Phöông phaùp keá toaùn
° Trong phöông phaùp keá toaùn cuûa phaân tích khaáu hao, chuùng ta ñònh
giaù (charge) khaùc nhau cho caùc thao taùc khaùc nhau.
Ta coù theå ñònh giaù cho moät thao taùc cao hôn hay thaáp hôn phí toån
thöïc söï cuûa noù.
– Ñònh nghóa: Soá löôïng maø ta ñònh giaù cho moät thao taùc ñöôïc goïi
laø phí toån khaáu hao cuûa noù.
– Ñònh nghóa chi phí traû tröôùc hay credit laø chi phí khaáu hao tröø
chi phí thöïc söï.
°
Ñeå cho chi phí khaáu hao toång coäng laø chaän treân leân chi phí
thöïc söï toång coäng thì taïi moïi thôøi ñieåm credit toång coäng phaûi
0.
°
Nhöng credit cho moät thao taùc caù bieät coù theå < 0 .
12.9.2004
Ch. 2: Amortized Analysis
13
Phöông phaùp keá toaùn: phaân tích stack
° Caùc thao taùc leân moät stack
– PUSH(S, x)
– POP(S)
– MULTIPOP(S, k) (POP k phaàn töû töø stack S)
° Duøng phöông phaùp keá toaùn ñeå xaùc ñònh chi phí khaáu hao cuûa moãi
thao taùc leân moät stack (ban ñaàu stack laø troáng).
– Nhaéc laïi: phí toån thöïc söï cuûa caùc thao taùc laø
°
°
°
PUSH
POP
MULTIPOP
goïi)
1
1
min(k, s), (s laø soá phaàntöû trong S khi ñöôïc
– Ta quy cho caùc thao taùc caùc phí toån khaáu hao nhö sau
°
°
°
PUSH
POP
MULTIPOP
2
0
0
laø moät haèng soá.
12.9.2004
Ch. 2: Amortized Analysis
14
Phöông phaùp keá toaùn: phaân tích stack (tieáp)
– Ta chöùng toû raèng coù theå traû cho moät chuoãi thao taùc baát kyø khi
tính giaù theo caùc phí toån khaáu hao. (Duøng 1 ñoàng ñeå töôïng tröng
1 ñôn vò phí toån.)
Moâ hình stack baèng moät choàng ñóa.
°
Giaû söû thao taùc laø PUSH: traû 2 ñoàng, trong ñoù
– duøng 1 ñoàng ñeå traû cho phí toån thöïc söï
– duøng 1 ñoàng coøn laïi ñeå traû tröôùc phí toån cho POP sau naøy
(neáu coù). Ñeå ñoàng naøy trong ñóa ñöôïc pushed vaøo choàng
ñóa.
°
°
Giaû söû thao taùc laø POP: khoâng caàn traû, maø
– duøng 1 ñoàng ñaõ ñöôïc traû tröôùc khi traû cho PUSH. Ñoàng
naøy naèm trong ñóa ñöôïc popped khoûi choàng ñóa.
Giaû söû thao taùc laø MULTIPOP: khoâng caàn traû, maø
– duøng 1 ñoàng ñaõ ñöôïc traû tröôùc khi traû cho PUSH.
12.9.2004
Ch. 2: Amortized Analysis
15
Phöông phaùp keá toaùn: phaân tích stack (tieáp)
° Keát luaän: Cho moät chuoãi baát kyø goàm n thao taùc PUSH, POP, vaø
MULTIPOP, phí toån khaáu hao toång coäng laø moät caän treân cho phí toån
thöïc söï toång coängï.
– Vì moãi thao taùc coù phí toån khaáu hao laø O(1) neân moät caän treân
cho phí toån thöïc söï toång coäng laø O(n).
12.9.2004
Ch. 2: Amortized Analysis
16
Phöông phaùp keá toaùn: phaân tích moät boä ñeám nhò phaân
° Phaân tích moät chuoãi caùc thao taùc INCREMENT leân moät boä ñeám nhò
phaân daøi k-bit maø trò ban ñaàu laø 0.
° Duøng phöông phaùp keá toaùn ñeå xaùc ñònh chi phí khaáu hao cuûa
INCREMENT
– Quy moät phí toån khaáu hao laø 2 ñoàng ñeå set moät bit thaønh 1.
°
duøng 1 ñoàng ñeå traû phí toån thöïc söï
°
duøng 1 ñoàng coøn laïi ñeå traû tröôùc cho phí toån ñeå reset bit naøy
thaønh 0 sau naøy (neáu coù).
12.9.2004
Ch. 2: Amortized Analysis
17
Phöông phaùp keá toaùn: phaân tích moät boä ñeám nhò phaân
° Xaùc ñònh phí toån khaáu hao cuûa INCREMENT (tieáp)
– Phí toån khaáu hao cuûa INCREMENT:
°
Phí toån cho resetting caùc bits trong voøng laëp while ñöôïc traû
baèng caùc ñoàng ñaõ ñöôïc traû tröôùc khi bit ñöôïc set.
°
Nhieàu nhaát laø 1 bit ñöôïc set.
– Vaäy phí toån khaáu hao cuûa INCREMENT toái ña laø 2 ñoàng.
° Vaäy chi phí khaáu hao cho n thao taùc INCREMENT laø O(n).
– Vì toång soá tieàn traû tröôùc khoâng bao giôø aâm (= soá caùc bit coù trò laø
1 trong boä ñeám) neân chi phí khaáu hao toång coäng laø caän treân cho
chi phí thöïc söï toång coäng.
12.9.2004
Ch. 2: Amortized Analysis
18
Phöông phaùp theá naêng
° Phaân tích moät chuoãi caùc thao taùc leân moät caáu truùc döõ lieäu.
– Cho moät caáu truùc döõ lieäu maø n thao taùc thöïc thi leân ñoù. Ban ñaàu
caáu truùc döõ lieäu laø D0
– Goïi ci laø chi phí thöïc söï cuûa thao taùc thöù i, vôùi i = 1,..., n.
– Goïi Di laø caáu truùc döõ lieäu coù ñöôïc sau khi aùp duïng thao taùc thöù i
leân caáu truùc döõ lieäu Di − 1 , vôùi i = 1,..., n.
thao taùc thöù 1
thao taùc thöù i
...
D0
D1
Di − 1
Di
12.9.2004
Ch. 2: Amortized Analysis
19
Phöông phaùp theá naêng (tieáp)
° Ñònh nghóa moät haøm soá
: {D0 ,..., Dn} → , vôùi laø taäp hôïp caùc soá thöïc.
Haøm ñöôïc goïi laø (haøm) theá naêng (potential function).
Trò (Di ) ñöôïc goïi laø theá naêng cuûa caáu truùc döõ lieäu Di , i =
0,...,n.
° Ñònh nghóa: phí toån khaáu hao (amortized cost) cuûa thao taùc thöù i laø
c^i = ci + (Di ) − (Di − 1 )
(*)
12.9.2004
Ch. 2: Amortized Analysis
20
Tải về để xem bản đầy đủ
48 trang
15540
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Phân tích thiết kế giải thuật - Chương 2: Phân tích khấu hao (Amortized Analysis)", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_phan_tich_thiet_ke_giai_thuat_chuong_2_phan_tich_k.ppt
