Giải thuật - 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.)