TAILIEUCHUNG - 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! | 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. Ch. 2 Amortized Analysis 2 Sơ lược Ba phương pháp để xác định phí tổn khấu hao gộp chung the aggregate method kế toán the accounting method 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 dài k bits bảng động. 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 STACK-EMPTY S and k 0 2 do POP S 3 k k 1 Ch. 2 Amortized Analysis 4 Cấu trúc dữ liệu stack tiếp Minh họa thao tác MULTIPOP top 23 33 MULTIPOP S 4 4 45 MULTIPOP S 7 4 top 4 78 78 - - - Ch. 2 Amortized Analysis 5 Bộ đếm nhị phân dài k bit Bộ đếm nhị phân dài k-bit k-bit binary counter là một mảng A 1 của các bit có độ dài length A là k. Ch. 2 Amortized Analysis 6 Bộ đếm nhị phân dài k bit tiếp Dùng bộ đếm để trữ một số nhị phân x x A k 1 2k 1 A 0 20 INCREMENT cộng 1 vào trị đang có trong bộ đếm modulo 2k INCREMENT A 0 1 1 1 1 0 0 0 Thủ tụ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 Ch. 2 Amortized Analysis 7 Phân tích một stack Bài toán xác định thời gian chạy của một chuỗi n thao tác lên một stack ban đầu stack là trống . Giải bằng phân tích thô sơ Phí tổn trong trường hợp xấu nhất của .

• Cơ sở dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu và giải thuật
• Phân tích khấu hao
• Phí tổn khấu hao
• Cấu trúc dữ liệu stack
• Bộ đếm nhị phân
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• tài liệu Cấu trúc dữ liệu và giải thuật
• giáo trình Cấu trúc dữ liệu và giải thuật
• bài tập Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu
• Ngôn ngữ diễn đạt giải thuật
• Thiết kế và phân tích giải thuật
• Giải thuật đệ quy
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu cơ bản
• Kiểu dữ liệu trừu tượng
• Tổng quan về giải thuật
• Kiểu dữ liệu
• Các tiêu chuẩn đánh giá dữ liệu
• Cách diễn đạt giải thuật
• Phân tích giải thuật
• phân tích thiết kế
• thiết kế hướng đối tượng
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm