Die Webseiten der Fachschaft Informatik am ERG SaalfeldZeitkomplexität
1. Erläuterung / Beschreibung
2. Landau-Notation
|
Grenze n | 200 | 300 | 400 | 500 | 600 | 700 | 800 | ||
Zeit t in Sekunden | 3 | 8 | 19 | 32 | 55 | 86 | 126 |
Im Diagramm sieht das so aus:
Damit läßt sich für den Zusammenhang zwischen n und t eine Potenzfunktion vermuten, z.B. t(n) ~ n2 oder t(n) ~ n3 oder, oder, oder?
Dazu untersuchen wir die unsere Werte aus der Tabelle auf entsprechende Quotienten:
Grenze n 200 300 400 500 600 700 800 Zeit t in Sekunden 3 8 19 32 55 86 126 n2 / t 13.333 11.250 8.421 7.812 6.545 5.697 5.079 n3 / t 2.666.666 3.375.000 3.368.421 3.906.250 3.927.272 3.988.372 4.063.492
Man erkennt deutlich, dass für n2 / t der Quotient nichtmal annähernd konstant ist. Bei n3 / t scheint sich
der Quotient bei 4.000.000 einzupegeln. Um das genauer zu verifizieren, habe ich zusätzlich die Zeiten für n = 1000 und n = 2000
bestimmt. Damit ergibt sich folgende Tabelle.
Grenze n 200 300 400 500 600 700 800 1000 2000 Zeit t in Sekunden 3 8 19 32 55 86 126 232 1865 n3 / t 2.666.666 3.375.000 3.368.421 3.906.250 3.927.272 3.988.372 4.063.492 4.310.344 4.289.544
Damit ist hinreichend genau bestätigt, dass für diesen Algorithmus n3 / t = constant gilt und damit t ~ n3 oder O(n3).
Wir betrachten jetzt das Programm mit 2 (kleinen) Änderungen:
use strict;
use warnings;
my $grenze = $ARGV[0];
for (my $a = 1; $a < $grenze; $a++) {
for (my $b = 1; $b < $grenze; $b++) {
for (my $c = 1; $c < $grenze; $c++) {
if ($c**2 == $a**2 + $b**2) {
print " $a \t $b \t $c \n";
}
}
}
}
Hierbei wurde im Vergleich zur Ausgangsvariante Folgendes geändert:
1. Die innere Schleife läuft nur noch von 1 bis zu $grenze. Das bedeutet, diese Schleife läuft nur noch halb so lange.
2. Die zweite Schleife (also die mit $b) beginnt jetzt auch mit 1 und nicht mehr bei $a. Das bedeutet, diese läuft jetzt im Schnitt doppelt so lang.
Das bedeutet, dass durch die Änderung der inneren Schleife sich die Anzahl der Aufrufe für die if-Anweisung im Vergleich zur 1. Version halbiert und
durch die 2. Änderung sich die Anzahl der Aufrufe für die if-Anweisung wieder verdoppelt. Das bedeutet, die beiden Änderungen heben sich
in Hinblick auf den Zeitbedarf gegenseitig auf.
Um jetzt die Zeitkomplexität zu ermitteln gehen wir davon aus, dass als Parameter eine Zahl eingegeben wird, die wir jetzt n nennen.
Dann wird die äußere Schleife (also die mit $a) n-mal durchlaufen bzw. wird die Schleife mit $b n-mal aufgerufen.
Die zweite Schleife (also die mit $b) wird auch n-mal durchlaufen bzw. wird die Schleife mit $c n-mal aufgerufen.
Die dritte Schleife (also die mit $c) wird auch n-mal durchlaufen bzw. wird die if-Anweisung n-mal aufgerufen.
Insgesamt wird als die if-Anweisung n * n * n oder n3 -mal aufgerufen. Da die Zeit für die if-Anweisung als konstant
betrachtet werden kann, erhalten wir durch diese Überlegungen t ~ n3 oder O(n3).
Das Programm für die pythagoräischen Zahlentripel wird auf einen alten Computer gestartet. Als Parameter wird 600 eingegeben. Da dieser Rechner schon etwas betagt ist, braucht er dafür 80s. Es soll jetzt berechnet werden, wie lange der Computer braucht, wenn als Parameter 3000 eingegeben wird.
Gegeben ist: n1 = 600, n2 = 3000 das bedeutet, die Anzahl für n hat sich verfünffacht.
wegen O(n3) bzw. t ~ n3 bedeutet das, dass die Zeit t2 das 125-fache des alten Wertes t1 ist (53 = 125).
Damit ist t2 das 125-fache von 80s gleich 10.000s! (Das sind rund 167 Minuten oder 2 Std. 47 min.)