Ü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?