3.) Beispiele zu jeder der drei Strategien:

Zur Erinnerung:

MF-Regel:
 Gefundenes Element an den Anfang der Liste.
T-Regel:
Vertausche gefundenes element mit seinem Listenvorgänger.
FC-Regel:
 Zähle mit, welches Element wie oft aufgerufen wurde und ordne die Elemente der Häufigkeit nach.

 

Beispiel : 1.)
Anm.:
 Das folgende Beispiel haben wir am Anfang für den Offline-Algorithmus bearbeitet, und Kosten von 280, also Durchschnittskosten von 4 erhalten.
   
   
Gegeben:
- 7 Elemente mit den Beschriftungen 1 bis 7
  - die Elemente sind der Reihe nach geordnet: 1,2,3,4,5,6,7
  - die Anfragenfolge1: ruft 10mal nacheinander 1 bis 7 auf
  - die Anfragenfolge2: ruft 10mal die 1, dann 10mal die 2,...,dann 10mal die 7 auf

Nach der MF-Regel ergibt sich folgendes:

Für Folge1:
Ergeben sich, wie man aus der Tabelle sieht, Kosten in der Höhe von 28+9*49= 469.
Als durchschnittliche Kosten pro Zugriff erhält man also: (469)/10*7 = 6,7.

Für Folge2:
Ergeben sich, wie man aus der Tabelle sieht, Kosten in der Höhe von: 21 + 10 * 7 = 91.
Als durchschnittliche Kosten pro Zugriff erhält man also: (91)/10*7 = 1,3.


=> die MF-Regel kann zu geringeren durchschnittlichen Kosten führen als die "beste"statische Anordnung.
Dies ist insbesondere dann der Fall, wenn die Bezeichnungen der Elemente in der Zugriffsfolge stark gebündelt sind.

Nach der T-Regel ergibt sich folgendes:

Für Folge1:
Ergeben sich, wie man aus der Tabelle sieht, Kosten in der Höhe von 28+29+30+7*31= 304.
Als durchschnittliche Kosten pro Zugriff erhält man also: (304)/10*7 was etwa 4,343 ist.

Für Folge2:
Ergeben sich, wie man aus der Tabelle sieht, Kosten in der Höhe von 10+11+13+17+20+25+31 = 127.
Als durchschnittliche Kosten pro Zugriff erhält man also: (127)/10*7, was etwa 1,81 ist.

Nach der FC-Regel ergibt sich folgendes:

Für Folge1:
Ergeben sich, wie man aus der Tabelle sieht, Kosten in der Höhe von 280
Als durchschnittliche Kosten pro Zugriff erhält man also: (280)/10*7 = 4.

Für Folge2:
Ergeben sich, wie man aus der Tabelle sieht, Kosten in der Höhe von 280.
Als durchschnittliche Kosten pro Zugriff erhält man also: (280)/10*7 = 4.


Beispiel : 2.)
   
Gegeben:
- 7 Elemente mit den Beschriftungen 1 bis 7
  - die Elemente sind der Reihe nach geordnet: 1,2,3,4,5,6,7
  - die Anfragenfolge: 7,2,7,3,3,7,4,4,4,7,5,5,5,5,7,6,6,6,6,6,7
  (der Offline-Algorithmus hat die Kosten: 58)

Nach der MF-Regel:
Ergeben sich, wie man aus der Tabelle sieht, Kosten in der Höhe von 52.
Als durchschnittliche Kosten pro Zugriff erhält man also: (52)/21, was etwa 2,476 ist.

Nach der T-Regel:
Ergeben sich, wie man aus der Tabelle sieht, Kosten in der Höhe von 95.
Als durchschnittliche Kosten pro Zugriff erhält man also: (95)/21, was etwa 4,524 ist.

Nach der FC-Regel:
Ergeben sich, wie man aus der Tabelle sieht, Kosten in der Höhe von 89.
Als durchschnittliche Kosten pro Zugriff erhält man also: (89)/21, was etwa 4,24 ist.