Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Lập Trình

Định lý ngón tĩnh (Static Finger Theorem) trong Cấu trúc dữ liệu

ĐỊNH LÝ NGÓN TĨNH (STATIC FINGER THEOREM) − Cho f là một phần tử cụ thể gọi là ngón (finger).

Thì biểu thức dưới đây là ranh giới trên chi phí của việc splay một chuỗi:

O(m + n log(n) + Σ Σ log (|f - i[j]| + 1))_j

CHÚ THÍCH − |f-i| là khoảng cách trong thứ tự đối xứng (symmetric ordering) của các mục giữa ngón và mục i.

Trong đó m là số phép cập nhật hoặc truy cập (access/update operations) trên cây có tối đa n nút.

Quan sát rằng, ít nhất theo nghĩa khấu hao (amortized sense), thời gian cho m phép toán đầu tiên trên cây không bao giờ vượt quá n nút là tương tự như thời gian cho cây tìm kiếm nhị phân cân bằng như AVL, 2-3 tree, v.v.