Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 có nội dung trình bày về phân tích khấu hao, các phương pháp để xác định phí tổn khấu hao, cấu trúc dữ liệu stack, bộ đếm nhị phân dài k bit, phân tích một stack,... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 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 do POP(S) 3 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 MULTIPOP(S, 4) 4 45 MULTIPOP(S, 7) 4 top  4 78 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) 0 1 1 1 1 0 0 0 – Thuû tuïc 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 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(n ). 2 ° 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] n/2 bit A[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ù ...