Online Computation Compet Analysis

[id:lethevert:20071004:p1]の本だけれど、10ページくらい読んだところで、どうにも証明が理解できなくて困っている。MTFが2-competitiveであることの証明なのだけれど。
原論文を探してみたら、http://www.cs.cmu.edu/~sleator/papers/Amortized-Efficiency.htmというのがそれらしいので、ちょっと読んでみる。

      • -

その前に、paid transpositionとfree transpositionの正確な意味を理解できていないというのが問題なのか。

      • -

However, immediately after accessing or inserting an item, we allow this item to be moved free of charge to any location closer to the front of the list.
Online Computation Compet Analysis

という文を、「リストの先頭に近いところに移動させるのはコストがかからない」という風に読んで混乱していたのだけれど、よく考えたら、「アクセスした要素の位置よりもリストの先頭側ならばどこに移動させるにもコストがかからない」という意味だった。これがfree transpositionで、この逆側に移動させるのがpaid transpositionだ。
違った。

In addition to performing access, insert, and delete operations, we may occasionally want to rearrange the list by exchanging pairs of consecutive items.
Amortized Efficiency Of List Update and Paging Rules

というのがtranspositionで、先のfree transposition以外はすべてpaid transpositionという意味だった。これには、アクセスや挿入や削除した要素とは無関係な要素に対する操作も含むということなのだろう。だとすると、少し理解ができてきた。