Komplexitätsberechnungen sollen von spezieller Hardware abstrahieren und zu einer möglichst einfachen Beziehung zwischen Problemgröße und Rechenzeit führen.
a) Finden Sie heraus, worin der Unterschied zwischen der Komplexität eines Problems und der Komplexität eines
Algorithmus besteht.
b) Stellen Sie jeweils einen Vertreter der Komplexitätsklassen O(log(n)), O(n), O(n log(n)), O(n2) und O(2n)
im Wertebereich 0 ≤ n ≤10 mit einem Funktionsplotter Ihrer Wahl graphisch dar.
c) Für die Bearbeitung einer Adressverwaltung stehen zwei Algorithmen A1 und A2 zur Auswahl, deren Ausführungsdauer nur von der Anzahl zu bearbeitender Adressen n abhängt. Die Ausführung von Algorithmus A1 benötigt s1 = (n+1)2 -2n Rechenschritte und die Ausführung von Algorithmus A2 benötigt s2 = 200+480 log(n)
Rechenschritte (wobei log(n) den natürlichen Logarithmus bezeichnet).
Geben Sie die Komplexitätsklassen O(s1) und O(s2) an und beurteilen Sie die Algorithmen. Welchen Algorithmus
würden Sie bevorzugen, wenn 20 Adressen bearbeitet werden sollen? Würde sich Ihre Auswahl ändern, wenn
die Anzahl an Adressen zunimmt?
