Übungen
Aufgabe 1: Effizienz untersuchen
Betrachte die folgenden Python-Programme zum Potenzieren:
Programm 1:
def pot(x, n):
p = 1
i = 0
while i < n:
p = p * x
i = i + 1
return p
Programm 2:
def pot(x, y):
p = 1
while y > 0:
if y % 2 == 1:
p = p * x
x = x * x
y = y // 2
return p
Welcher zugrunde liegende Algorithmus ist effizienter? Untersuche dies mit Hilfe von Zählvariablen und Laufzeitmessungen.
Aufgabe 2: Effizienz verbessern
Betrachte den folgenden Algorithmus zum Primzahltesten:
Warum ist das hier benutzte Verfahren nicht sehr effizient?
Wie könnte man den Algorithmus effizienter gestalten?
