Theoretische Informatik?

Hallo leute,

weiß jemand wie man das darstellt?

Man muss die Laufzeit in 0-Notation bestimmen von dem Algorithmus ggT (größten gemeinsamen Teilers). Also Schritt für Schritt z.B:

0(1)

0(1) => T(0) = 0(1)

......

wäre super wenn das jemand könnte. :)

Lg

Answer 1

[ralphdieter]

Meine Vermutung: Der Algorithmus terminiert spätestens nach max(x,y) Schritten, und jeder Schritt ist in 𝓞(1). Damit läge er in 𝓞(x+y).

Für ggT(1,y) wird diese Grenze offensichtlich erreicht. Du musst nur noch zeigen, dass der Algorithmus

• für ggT(x,y) mit 1<x<y nie länger braucht als für ggT(1,y).
• für ggT(y,x) nie länger braucht als für ggT(x,y).

Comments

[Ralfseg]

Danke! Das Problem ist ich weiß nicht ganz wie ^^

[ralphdieter]

@Ralfseg

Durch Induktion: Bei jedem rekursiven Aufruf wird max(x,y) um mindestens 1 kleiner.

Im Fall if (x<y) then ...“:

x<y (Voraussetzung) ∧ y–x<y (wegen x>0) ⇒ max(x,y–x) < y

Für x>y geht's analog.

[Ralfseg]

@ralphdieter

Ok danke. Also ist die Laufzeit jetzt O(x+y) . Ich habe auch woanders gesehen das die Laufzeit O(n^2) ?

[ralphdieter]

@Ralfseg

Was ist n? Vielleicht handelt es sich um eine andere Implementierung. Ich sehe jedenfalls keinen Fehler in meinen Überlegungen.

So nebenbei: 𝓞(n)⊂𝓞(n²).

[Ralfseg]

@ralphdieter

Ok danke. Ist dies auch möglich bzw. es ist ja das was Sie eigentlich geschrieben haben . Oder? ^^

Die Anzahl der Iterationen (d.h. Anzahl der Rekursionsaufrufe plus 1) ist höchstens x + y − 1 und damit ist die Laufzeit O(x + y).  Die Summen z = x + y (wobei x, y ≥ 1 sind) werden stufenweise immer kleiner und sind natürliche Zahlen.

z = x +y =⇒ z ′ = (x −y) +y = x < z ∨z ′ = x + (y −x) = y < z und z, z ′ ∈ N.

Bei x = y ≥ 1 haben wir keinen weiteren Rekursionsaufruf und der kleinste Summenwert ist 2. Daraus folgt, dass im Worst Case die Anzahl der Iterationen (d.h. Anzahl der Rekursionsaufrufe plus 1) höchstens x + y − 1 ist.

[ralphdieter]

@Ralfseg

Passt soweit, bis auf:

Bei x = y ≥ 1 haben wir keinen weiteren Rekursionsaufruf und der kleinste Summenwert ist 2. Daraus folgt,

gar nichts, denn x=y=1 ist nur ein Einzelfall. Für eine wirksame Untergrenze brauchst Du beliebig große x und y.

Mach es lieber etwas formaler mit vollständiger Induktion:

• Behauptung: ... (höchstens x+y−1 Rekursionen)
• Induktionsanfang: ... (stimmt für x+y=2)
• Induktionsschritt: ... (stimmt für alle x+y≤n ⇒ stimmt für x'+y'=n+1)

Perfekt wird's, wenn Du noch die Worst-Cases (1,y) und (x,1) angibst und so zeigst, dass die Abschätzung 𝓞(x+y) nicht mehr verbessert werden kann (weil Du da wirklich y bzw. x Rekursionsschritte brauchst).

Answer 2

[jort93]

Um das zu machen bräuchte man wohl den Algorithmus.

Kommt ja logischerweise auf die Implementation an.

Comments

[Ralfseg]

Stimmt habe soeben die Frage bearbeitet . :)