(Analisi complessità)
Difference between online (real-time) and offline algorithms:
- an online algorithm A executes the given operation without any knowledge of the future incoming operations
- an offline algorithm knows the whole sequence in advance
An online algorithm is $\alpha$-competitive if exists a constant $k$ such that for any incoming sequence of operations $S$ we have that $C_A(S) \le \alpha C_{\text{offline}} + k$ where $C_{\text{offline}}$ is the optimal offline algorithm.
Self-organizing lists. Elements that are accessed frequently will be in front of the list.
MTF algorithm is $4$-competive with an offline algorithm (that's good).
In this video MTF is used to cache voxels in a rendering engine .