Phân tích Amortized (Amortize Analysis)
Phân tích này dùng khi thao tác thỉnh thoảng rất chậm, nhưng hầu hết thao tác thường xuyên thì nhanh. Trong cấu trúc dữ liệu, cần amortized analysis cho Hash Tables, Disjoint Sets, v.v.
Ví dụ Hash table: tìm kiếm/insert đa số O(1), nhưng khi va chạm (collision) cần O(n) để giải quyết.
Phương pháp tổng hợp (Aggregate Method)
Dùng để tìm chi phí tổng. Nếu thêm một loạt dữ liệu, chi phí trung bình:
$$\frac{Cost(n \text{ operations})}{n} = \frac{Cost(\text{normal}) + Cost(\text{expensive})}{n}$$
Ví dụ: Mảng động (Dynamic Array)
Chèn tại index cho trước O(1). Nhưng nếu index không có, thất bại. Lúc đó, gấp đôi kích thước mảng rồi chèn nếu index hợp lệ.
Cho cᵢ = chi phí lần chèn thứ i.
$$c_i = 1 + \begin{cases} i-1, & \text{nếu } i-1 \text{ là lũy thừa của 2} \\ 0, & \text{ngược lại} \end{cases}$$
$$\frac{\sum_{i=1}^n c_i}{n} \le \frac{n + \sum_{j=1}^{\lfloor \log_2(n-1) \rfloor} 2^j}{n} = \frac{O(n)}{n} = O(1)$$
Vậy chi phí trung bình chèn vào mảng động là O(1).