Đang chuẩn bị liên kết để tải về tài liệu:
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! | 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 lt length A and A i 1 3 do A i 0 4 i i 1 5 if i lt 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 .