Aktionen zählen

Ein Python-Programm mit Zählvariablen

Um den Aufwand eines Algorithmus grob abzuschätzen, reicht es manchmal, die wichtigsten Aktionen zu zählen. Das folgende Python-Programm zählt die Schleifendurchläufe bei der Ausführung des Wechselwegnahme-Algorithmus.

# Funktionsdefinition

def ggt(x, y):
    z = 0            # Schleifenzähler initialisieren
    while x != y:
        z = z + 1    # Schleifenzähler hochzählen
        if x > y:
            x = x - y
        else:
            y = y - x
    return (x, z)

# Test mit Schleifenzählung

a = 44
b = 8
(ergebnis, zaehler)  = ggt(a, b)
print('ggt(', a, ',', b, ') =', ergebnis)
print('Schleifendurchläufe: ', zaehler)

Startet man das Programm, so erhält man - nach etwas Wartezeit - das folgende Ergebnis:

>>> 
ggt( 44 , 8 ) = 4
Schleifendurchläufe:  6

Aufgabe 1

(a) Probiere das selbst aus. Bestimme entsprechend die Anzahl der Schleifendurchläufe für a = 44 und b = 8 beim Euklidischen Algorithmus.

(b) Bestimme auch die Anzahl der Schleifendurchläufe bei beiden Algorithmen für a = 3642431875 und b = 15. Kannst du erklären, warum es hier zu einem so großen Unterschied kommt?