Python - Phân tích khấu hao
Phân tích khấu hao bao gồm việc ước tính thời gian chạy cho chuỗi hoạt động trong một chương trình mà không tính đến khoảng thời gian phân phối dữ liệu trong các giá trị đầu vào. Một ví dụ đơn giản là việc tìm một giá trị trong danh sách được sắp xếp nhanh hơn so với trong danh sách không được sắp xếp. Nếu danh sách đã được sắp xếp, nó không quan trọng dữ liệu được phân phối như thế nào. Nhưng tất nhiên độ dài của danh sách có tác động vì nó quyết định số bước mà thuật toán phải trải qua để có được kết quả cuối cùng.
Vì vậy, chúng ta thấy rằng nếu chi phí ban đầu của một bước duy nhất để có được danh sách được sắp xếp là cao, thì chi phí của các bước tìm kiếm phần tử tiếp theo sẽ thấp đáng kể. Vì vậy, phân tích khấu hao giúp chúng tôi tìm ra ràng buộc về thời gian hoạt động trong trường hợp xấu nhất cho một chuỗi hoạt động. Có ba cách tiếp cận để phân tích khấu hao.
Accounting Method- Điều này liên quan đến việc ấn định chi phí cho mỗi hoạt động được thực hiện. Nếu hoạt động thực tế kết thúc nhanh hơn thời gian được ấn định thì một số tín dụng dương sẽ được tích lũy trong phân tích. Trong trường hợp ngược lại, nó sẽ là tín dụng tiêu cực. Để theo dõi các khoản tín dụng tích lũy này, chúng tôi sử dụng cấu trúc dữ liệu dạng cây hoặc ngăn xếp. Các nghiệp vụ được thực hiện sớm (như sắp xếp danh sách) có chi phí khấu hao cao nhưng các hoạt động thực hiện muộn có chi phí khấu hao thấp hơn do tín dụng lũy kế được sử dụng. Vì vậy, chi phí phân bổ là một giới hạn trên của chi phí thực tế.
Potential Method- Trong phương pháp này, tín dụng đã lưu được sử dụng cho các hoạt động trong tương lai dưới dạng hàm toán học về trạng thái của cấu trúc dữ liệu. Đánh giá của hàm toán học và chi phí phân bổ phải bằng nhau. Vì vậy, khi chi phí thực tế lớn hơn chi phí khấu hao thì tiềm năng sẽ giảm và nó được sử dụng cho các hoạt động sau này vốn tốn kém.
Aggregate analysis - Trong phương pháp này, chúng tôi ước tính giới hạn trên trên tổng chi phí của n bước. Chi phí phân bổ là một phép chia đơn giản giữa tổng chi phí và số bước (n) ..