# euklidischer / naiver Algorithmus



## Lukases2 (30. Apr 2015)

Aufgabe: Zeigen Sie: Der euklidische Algorithmus benötigt höchstens einen Schritt mehr (= eine Iteration der Schleife mehr) als der naive Algorithmus. 

naiver Algorithmus:
1. Falls n = m, setze g auf m und beende die Rechnung. Andernfalls
führe Schritt (2) aus.
2. Falls n > m, ersetze n durch n - m und führe Schritt (1) aus.
Andernfalls führe Schritt (3) aus.
3. Ersetze m durch m - n und führe Schritt (1) aus.

eulidischer Algorithmus:
1. Falls m = 0, dann setze g auf n und beende die Rechnung.
Andernfalls führe Schritt (2) aus.
2. Setze a auf m,
setze b auf n mod m,
setze n auf a,
setze m auf b und
führe Schritt (1) aus.

Als erstes verstehe ich jetzt nicht so ganz, wann der eulidische Algorithmus einen Schritt mehr braucht, als der naive. Eigentlich ist doch der euklidische Algorithmus schneller?
Wie gehe ich weiter an die Aufgabe heran? Einen wirklichen Lösungsansatz habe ich noch nicht gefunden.


----------



## fhoed (2. Mai 2015)

Hallo Lukases2,

ich hoffe ich kann dir helfen.
(Die Lösung ist im Screenshot...)



Übrigens: 1 Minute Google>Wikipedia> Euklidischer Algorithmus#Laufzeitanalyse


Lg,

f


----------

