Theo lý thuyết độ phức tạp tính toán, phương pháp tiềm năng được định nghĩa là phương pháp được thực hiện để phân tích độ phức tạp về thời gian và không gian được phân bổ của cấu trúc dữ liệu, một thước đo hiệu suất của cấu trúc đó qua các chuỗi hoạt động nhằm loại bỏ chi phí của các hoạt động không thường xuyên nhưng tốn kém.
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 được coi là trạng thái của cấu trúc dữ liệu, Φ (S) biểu thị công việc đã được hạch toán trong phân tích khấu hao nhưng chưa được thực hiện. Do đó, Φ (S) có thể được hình dung như tính lượng năng lượng tiềm năng được lưu trữ ở 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 xác định bằng 0. Ngoài ra, Φ (S) có thể được hình dung như đại diện cho lượng rối loạn ở trạng thái S hoặc khoảng cách của nó so với trạng thái lý tưởng.
Ví dụ
Hãy để chúng ta có thể biểu thị một hàm tiềm năng Φ (đọc là "Phi") trên các trạng thái của cấu trúc dữ liệu thỏa mãn các thuộc tính sau -
- Φ (a0) =0, trong đó a0 là trạng thái bắt đầu của cấu trúc dữ liệu.
- Φ (at) ≥ 0 cho tất cả các trạng thái tại cấu trúc dữ liệu xảy ra tại thời điểm tính toán.
Một cách trực quan, hàm tiềm năng sẽ có thể theo dõi thời gian tính phí trước tại bất kỳ thời điểm nào trong quá trình tính toán. Nó đo lượng thời gian tiết kiệm có sẵn để trả cho các hoạt động tốn kém. Nó giống như số dư ngân hàng trong phương pháp của chủ ngân hàng. 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 nào đưa nó vào trạng thái đó.
Sau đó, chúng tôi xác định thời gian khấu hao của một hoạt động là
c + Φ (a ') - Φ (a),
trong đó c là chi phí ban đầu của hoạt động và a và a 'lần lượt là trạng thái của cấu trúc dữ liệu trước và sau hoạt động. Do đó, thời gian phân bổ được xác định là thời gian thực tế cộng với sự thay đổi của giá trị tiềm năng. Tốt nhất, nên xác định Φ sao cho thời gian khấu hao của mỗi hoạt động phải nhỏ. Do đó, thay đổi về tiềm năng nên được đo lường là tích cực đối với hoạt động chi phí thấp và tiêu cực đối với hoạt động chi phí cao.