(Exkurs)
Vergleichen Sie die Ausführungsgeschwindigkeiten der Lösungen zu den Aufgaben 3-1 und 3-2.
Zeitmessungen auf einer Referenzmaschine (JVM 1.5.0_13, Intel Core 2 Duo 2,4 GHz) mit je 100 Versuchen ergeben:
zu den Teilaufgaben:
Bei den Ergebnissen zu Variante 3-2 sehen ist das bei der seuqntiellen Suche zu erwartende, annähernd lineare Laufzeitverhalten zu beobachten: Beim Verdoppeln der Problemgröße (Listenlänge) verdoppelt sich auch die Ausführungszeit mehr oder weniger.
Variante 3-1 hat offensichtlich einen enorm viel schneller steigenden Zeitbedarf. Schuld daran ist die Verwendung der get-Methode der LinkedList: Weil auf einer linearen verketteten Liste kein direkter Zugriff auf die einzelnen Elemente anhand ihres Indexes möglich ist, muss die get-Methode jedes Mal am Anfang der Liste anfangen und sich Element für Element so lange „durchhangeln,“ bis der gewünschte Index erreicht ist.
Die get-Methode wird nun aber in einer engen for-Schleife aufgerufen, im schlimmsten Fall für jedes Element einmal. Bei jedem dieser Durchläufe muss die get-Methode sich nun vom Listenanfang an bis zum gesuchten Index durchhangeln..! Das führt schnell zu einer Explosion der benötigten Zeit, wie im Messergebnis zu sehen ist.
Anders formuliert: Weil die lineare verkettete Liste keinen wahlfreien Zugriff auf ihre Elemente erlaubt, sondern nur sequentiellen Zugriff, hat schon die get-Methode eine Zeitkomplexität von O(n). Dieser Aufwand fällt aber bei jedem Durchlauf unserer for-Schleife jeweils einmal an, so dass sich diese Zeitkomplexität noch mal ver-n-facht, mit n = 15000 oder 30000. Da kommt schnell was zusammen…
zu Variante 3-1: O(n²)
zu Variante 3-2: O(n)