Phân tích khấu hao

Phân tích khấu hao giới hạn chi phí trung bình cho mỗi thao tác trên một chuỗi thao tác trong trường hợp xấu nhất, cho thấy rằng các thao tác đôi khi tốn kém có thể trở nên rẻ khi chi phí của chúng được phân bổ cho nhiều thao tác rẻ tiền.

Definition

Phân tích khấu hao là một phương pháp để giới hạn tổng chi phí của một chuỗi các thao tác trên một cấu trúc dữ liệu và chia cho số lượng thao tác, mang lại chi phí khấu hao trên mỗi thao tác được giữ trong trường hợp xấu nhất trên toàn bộ chuỗi ngay cả khi các thao tác riêng lẻ khác nhau rất nhiều về chi phí.

Scope

Chủ đề này bao gồm ba kỹ thuật tiêu chuẩn của phân tích khấu hao — phương pháp tổng hợp, phương pháp kế toán (ngân hàng) và phương pháp tiềm năng — và ứng dụng của chúng vào các cấu trúc dữ liệu có các thao tác riêng lẻ khác nhau về chi phí, chẳng hạn như mảng động, bộ đếm nhị phân, cây splay và cấu trúc tập hợp rời rạc (union-find). Nó phân biệt chi phí khấu hao với chi phí trường hợp trung bình và chi phí trường hợp xấu nhất trên mỗi thao tác.

Core questions

• Chi phí khấu hao khác với chi phí trường hợp xấu nhất trên mỗi thao tác và chi phí trường hợp trung bình như thế nào?
• Phương pháp tổng hợp giới hạn tổng chi phí của một chuỗi thao tác như thế nào?
• Phương pháp kế toán gán tín dụng để thanh toán cho các thao tác tốn kém sau này như thế nào?
• Phương pháp tiềm năng sử dụng hàm tiềm năng để làm phẳng chi phí như thế nào?
• Những cấu trúc dữ liệu nào dựa vào các đảm bảo khấu hao thay vì các giới hạn trên mỗi thao tác?

Key concepts

• chi phí khấu hao
• phương pháp tổng hợp
• phương pháp kế toán (ngân hàng)
• phương pháp tiềm năng
• hàm tiềm năng
• nhân đôi mảng động
• tăng bộ đếm nhị phân
• union-find với nén đường dẫn

Key theories

Phương pháp tiềm năng

Phương pháp tiềm năng gán một tiềm năng không âm cho trạng thái của cấu trúc dữ liệu; chi phí khấu hao của một thao tác là chi phí thực tế của nó cộng với sự thay đổi tiềm năng, do đó các thao tác rẻ tiền tạo ra tiềm năng để thanh toán cho các thao tác tốn kém sau này.

Phương pháp kế toán (ngân hàng)

Phương pháp kế toán tính phí một số thao tác cao hơn chi phí thực tế của chúng, lưu trữ phần dư dưới dạng tín dụng trên các phần tử cấu trúc dữ liệu để thanh toán cho các thao tác tốn kém trong tương lai, đảm bảo tín dụng không bao giờ âm.

Clinical relevance

Phân tích khấu hao giải thích tại sao nhiều cấu trúc được sử dụng rộng rãi lại hiệu quả trong thực tế mặc dù đôi khi có các thao tác tốn kém: mảng động (danh sách có thể thay đổi kích thước), bảng băm được băm lại, union-find được sử dụng trong các thuật toán kết nối và cây bao trùm tối thiểu, và các cấu trúc tự điều chỉnh như cây splay đều dựa vào các đảm bảo khấu hao chứ không phải đảm bảo trên mỗi thao tác.

History

Thuật ngữ và khuôn khổ hệ thống cho phân tích khấu hao được Robert Tarjan giới thiệu vào năm 1985, dựa trên các lập luận ad hoc trước đó. Kỹ thuật này là trung tâm để phân tích các cấu trúc dữ liệu tự điều chỉnh (cây splay, đống Fibonacci) được Tarjan và Sleator phát triển vào những năm 1980.

Key figures

• Robert Tarjan
• Daniel Sleator

Seminal works

• tarjan1985amortized
• cormen2009

Frequently asked questions

Chi phí khấu hao có giống với chi phí trường hợp trung bình không?

Không. Chi phí trường hợp trung bình là một kỳ vọng trên một phân phối xác suất của các đầu vào và có thể bị vi phạm bởi một đầu vào không may mắn. Chi phí khấu hao là một đảm bảo trường hợp xấu nhất trên một chuỗi các thao tác mà không có sự ngẫu nhiên nào được giả định: tổng chi phí của bất kỳ chuỗi nào như vậy đều bị giới hạn, do đó mức trung bình trên mỗi thao tác luôn được giữ.

Tại sao việc nối vào một mảng động lại là O(1) khấu hao khi thay đổi kích thước là O(n)?

Bởi vì mảng thường tăng gấp đôi dung lượng của nó, việc thay đổi kích thước hiếm khi xảy ra so với việc nối, và tổng công việc sao chép trên một chuỗi n lần nối tỷ lệ thuận với n. Phân bổ cho tất cả các lần nối, điều đó mang lại chi phí khấu hao không đổi mặc dù một lần thay đổi kích thước duy nhất là tuyến tính.