Phân tích khấu hao
Phân tích này được sử dụng khi hoạt động không thường xuyên rất chậm, nhưng hầu hết các hoạt động đang thực hiện rất thường xuyên đều nhanh hơn. Trong Cấu trúc dữ liệu, chúng ta cần phân tích khấu hao cho Bảng băm, Tập rời rạc, v.v.
Trong Hash-table, phần lớn độ phức tạp của thời gian tìm kiếm là O (1), nhưng đôi khi nó thực hiện các phép toán O (n). Khi chúng ta muốn tìm kiếm hoặc chèn một phần tử trong bảng băm trong hầu hết các trường hợp, nhiệm vụ đó là thời gian cố định, nhưng khi xảy ra va chạm, nó cần các thao tác gấp O (n) lần để giải quyết xung đột.
Phương pháp tổng hợp
Phương pháp tổng hợp được sử dụng để tìm tổng chi phí. Nếu chúng ta muốn thêm một loạt dữ liệu, thì chúng ta cần tìm chi phí phân bổ theo công thức này.
Đối với một chuỗi n hoạt động, chi phí là -
$ \ frac {Chi phí (n \:hoạt động)} {n} =\ frac {Chi phí (bình thường \:hoạt động) + Chi phí (Đắt \:hoạt động)} {n} $
Ví dụ về Phân tích khấu hao
Đối với một mảng động, các mục có thể được chèn vào một chỉ mục nhất định trong thời gian O (1). Nhưng nếu chỉ mục đó không có trong mảng, nó không thể thực hiện tác vụ trong thời gian liên tục. Đối với trường hợp đó, ban đầu nó tăng gấp đôi kích thước của mảng, sau đó sẽ chèn phần tử vào nếu có chỉ mục.
Đối với mảng động, hãy đặt ci =chi phí chèn thứ i.
$ So \:ci =1 + \ begin {case} i \:- \:1, if \:i-1 \:is \:power \:of \:2 \\ 0, \:\:\:\ :\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:Nếu không thì \ end {case} $
$$ \ frac {\ displaystyle \ sum \ limit_ {i =1} ^ n ci} {n} \ leq \ frac {n + \ displaystyle \ sum \ limit_ {j =1} ^ {\ lfloor \ log {2} { \ lgroup n-1 \ rgroup} \ rfloor} 2j} {n} =\ frac {O \ lgroup n \ rgroup} {n} $$