Vấn đề tính toán chi phí trung bình
Tính chi phí trung bình của thao tác meld là một nhiệm vụ khó khăn. Khó khăn chính nằm ở việc tích lũy cho sự biến thiên lớn của chi phí một thao tác thực hiện tại các thời điểm khác nhau trong một chuỗi ngẫu nhiên các thao tác. Mặc dù mục tiêu thiết kế bị ảnh hưởng bởi chi phí của chuỗi thao tác, định nghĩa khái niệm chi phí trung bình của một thao tác dựa trên chi phí của các chuỗi thao tác không dẫn đến kết quả gì. Việc triển khai một hàm tiềm năng (potential function) để bù trừ sự biến thiên của chi phí thực tế là cách lý tưởng để xử lý tình huống này. Trong phần tiếp theo chúng ta thảo luận khái niệm chi phí trung bình.
Định nghĩa chi phí trung bình
Cho B là một kiểu dữ liệu trừu tượng (ADT) với các thao tác cơ bản P = {P₁, P₂, …, Pₖ} và DS là cấu trúc dữ liệu triển khai B. Cho F là hàm tiềm năng được chỉ định trên các cấu hình của cấu trúc dữ liệu thành số thực không âm. Giả sử thêm rằng F(Φ) = 0. Cho DSʲ chỉ định cấu hình thu được nếu thực hiện thao tác Pₖ trên cấu hình DS, và C là chi phí thực tế của việc thực hiện Pₖ trên DS.
Khi đó, chi phí trung bình của Pₖ hoạt động trên DS, ký hiệu là a(Pₖ, DS), được cho bởi:
a(Pₖ, DS) = C + F(DSʲ) – F(DS)
Nếu a(Pₖ, DS) ≤ c·g(m) cho mọi cấu hình DS có kích thước m, ta kết luận chi phí trung bình của Pₖ là O(g(m)).