Online Computation Compet Analysis

昨日の件で、結局一番混乱していたのは、competitive analysisという概念をよく理解していなかったことらしいのだけれど、それは新しい本を読みはじめたときはよくあることなので。
そもそも、MTFがcompetitiveということのイメージがよく掴めなかったというところが端緒にあって、うまく理解できなかったっぽい。入力列の予測が立たないのに、リストの並べ変えを行うことでコストを改善することができるということが釈然としなかったのだ。
結局あれこれ考えて、これはコストモデルの立てかたに関係しているのだという結論に行き着いた。つまり、

のがに含まれるというところが味噌なのだろう。
って、この本を手元で見ている人しか意味の分からないことを書いてみた。