Giới thiệu
Theo lý thuyết độ phức tạp tính toán, phương pháp tiềm năng là một phương pháp dùng để phân tích độ phức tạp thời gian và không gian trung bình (amortized) của một cấu trúc dữ liệu – đo lường hiệu suất qua các chuỗi thao tác, loại bỏ chi phí của các thao tác hiếm nhưng đắt đỏ.
Trong phương pháp tiềm năng, một hàm Φ được chọn để chuyển đổi các trạng thái của cấu trúc dữ liệu thành các số không âm. Nếu S là trạng thái của cấu trúc dữ liệu, Φ(S) biểu thị công việc đã được tính toán trong phân tích amortized nhưng chưa thực hiện. Do đó, Φ(S) có thể hình dung như lượng năng lượng tiềm ẩn lưu trữ trong trạng thái đó. Trước khi khởi tạo cấu trúc dữ liệu, giá trị tiềm năng được định nghĩa là 0. Thay vào đó, Φ(S) có thể hình dung như biểu thị mức độ rối loạn của trạng thái S hoặc khoảng cách từ trạng thái lý tưởng.
Ví dụ
Giả sử chúng ta ký hiệu hàm tiềm năng Φ (đọc "Phi") trên các trạng thái của cấu trúc dữ liệu thỏa mãn:
- Φ(a₀) = 0, trong đó a₀ là trạng thái khởi đầu của cấu trúc dữ liệu.
- Φ(aₜ) ≥ 0 cho mọi trạng thái aₜ xảy ra trong quá trình tính toán.
Trực quan, hàm tiềm năng sẽ theo dõi thời gian đã "trả trước" tại bất kỳ điểm nào trong tính toán. Nó đo lường lượng thời gian tiết kiệm sẵn sàng để trả cho các thao tác đắt đỏ. Nó giống như số dư tài khoản trong phương pháp ngân hàng (banker's method). Nhưng thú vị là nó chỉ phụ thuộc vào trạng thái hiện tại của cấu trúc dữ liệu, bất kể lịch sử tính toán dẫn đến trạng thái đó.
Chúng ta định nghĩa thời gian trung bình của một thao tác là:
c + Φ(a') – Φ(a)
trong đó c là chi phí gốc của thao tác, a và a' là trạng thái của cấu trúc dữ liệu trước và sau thao tác. Do đó thời gian trung bình là thời gian thực tế cộng với thay đổi tiềm năng. Lý tưởng là Φ nên được định nghĩa sao cho thời gian trung bình của mỗi thao tác nhỏ. Do đó thay đổi tiềm năng nên dương cho thao tác chi phí thấp và âm cho thao tác chi phí cao.