Die Webseiten der Fachschaft Informatik am ERG Saalfeld
experimentelle Bestimmung der Zeitkomplexität
Es soll durch einen Versuch die Abhängigkeit der benötigten Zeit von der Anzahl
der Feldelemente bestimmt werden. Hier wird Selection-Sort verwendet. Um die Anzahl der Feldelemente
leicht ändern zu können, werden diese als Parameter übergeben. Die Felder werden nicht ausgegeben, denn
das würde nur Zeit kosten und das Ergebnis verfälschen (es geht ja um das Sortieren). Um die Zeit zu messen,
wird der Befehl time() verwendet. Es wird die Zeitdauer des Sortierens ausgegeben.
Das Programm zum Sortieren mit Selection-Sort sieht so aus:
Programm
use strict;
use warnings;
my $anz = $ARGV[0];
# wir erstellen/wuerfeln ein Feld
my @feld = ();
foreach ( 1 .. $anz ) {
push @feld, int(rand(300)) + 200;
}
my $zeit1 = time();
# Variablen für das Tauschen
my $help; # Hilfsvariable für das Tauschen
my $max; # der Wert des groessten Elements
my $stelle; # die Stelle des groessten Elements
# wir sortieren mit Selection-Sort
my $anzahl = scalar @feld;
my $feldende = $anzahl; # der Index wird gleich um 1 kleiner!
for (my $j = 0; $j < $anzahl; $j++) {
# Initialisieren für einen Durchlauf
$max = -100000; # da wir grossen Wert suchen, hier kleiner Wert
$stelle = -1; # ein Wert, den es im Feld nicht gibt
$feldende--; # Index vom Feldende 1 kleiner
# wir suchen in dem Feld von $feld[0] bis $feld[$feldende] die groesste Zahl
for (my $i = 0; $i <= $feldende; $i++) {
if ($feld[$i] > $max) {
$max = $feld[$i];
$stelle = $i;
}
}
# wir tauschen das groesste Element mit dem Element an der letzten Stelle
$help = $feld[$feldende];
$feld[$feldende] = $max;
$feld[$stelle] = $help;
}
my $zeit2 = time();
my $dauer = $zeit2 - $zeit1;
print "Anzahl: $anz \t Dauer: $dauer\n";
__END__
Der Aufruf sah bei mir so aus:
Aufgaben
- Bringen Sie das Programm zum Laufen.
- Informieren Sie sich über den Perl-Befehl time().
- Übertragen Sie die Änderungen auf Bubble-Sort.
- Erstellen Sie eine eigene Wertetabelle mit n und t.
- Erstellen Sie mit Ihren Werten ein Diagramm (auf der x-Achse die Anzahl, auf der y-Achse die benötigte Zeit)
- Stellen Sie eine Vermutung für die Abhängigkeit von n und t auf.
- Überprüfen Sie Ihre Vermutung durch Bestimmung eines geeigneten Quotienten (der sollte dann konstant sein).
Weblinks
- Bestimmung der Zeitkomplexität mit Java
- Perl - Date and Time
zurück
© ERG Saalfeld - Hans-Dietrich Kirmse 23.06.2015
|