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

from random import randint
import sys
import time

anz = int(sys.argv[1])

#Wir erstellen/würfeln ein Feld
feld = []
for a in range(anz):
    feld.append(randint(1,300)+200)

zeit1 = time.time()

print('\n')

#wir sortieren mit Selection-Sort
anzahl = len(feld)
fehlende = anzahl
for j in range(anzahl):
    max = -100000
    stelle = -1
    fehlende = fehlende - 1

    #Wir suchen in dem Feld von feld[0] bis feld[fehlende] die groesste Zahl
    for i in range (fehlende+1):
        if feld[i]>max:
            max = feld[i]
            stelle = i

    #Wir tauschen das groesste Element mit dem Element an der letzen Stelle
    help = feld[fehlende]
    feld[fehlende] = max
    feld[stelle] = help

zeit2 = time.time()
dauer = zeit2-zeit1
print('Anzahl:',anz,'\tDauer:',dauer)

Der Aufruf sah bei mir so aus:

Aufgaben

1. Bringen Sie das Programm zum Laufen.
2. Informieren Sie sich über den Befehl time().
3. Übertragen Sie die Änderungen auf Bubble-Sort.
4. Erstellen Sie eine eigene Wertetabelle mit n und t.
5. Erstellen Sie mit Ihren Werten ein Diagramm (auf der x-Achse die Anzahl, auf der y-Achse die benötigte Zeit)
6. Stellen Sie eine Vermutung für die Abhängigkeit von n und t auf.
7. Überprüfen Sie Ihre Vermutung durch Bestimmung eines geeigneten Quotienten (der sollte dann konstant sein).

Weblinks

1. Bestimmung der Zeitkomplexität mit Java

zurück