Vom Algorithmus zur Rekursionsgleichung

Question

Aufgabe:

Eingabe = n ∈ N (Natürliche Zahlen)

Ausgabe = keine

Algorithmus LINALG nicht rekursiv,liefert einen Wert vom Typ boolean und hat eine lineare Zeitkopmplexität

REKALG(n)

1 if n=1

2      then return

3 if LINALG(n)

4      then REKALG (⌊2n/3⌋)

5      else REKLAG(⌈n/3⌉)

a) Stellen Sie die Rekursionsgleichung zur Bestimmung der maximaleen Anzahl der rekursiven Auftrufe dieses Algorithmus mit dem Argument n auf. Zählen Sie die Auswertung der Anfangsbedinung auch als einen rekursiven Aufruf. ( Auf und Abrunden in der rekursionsgleichung vernachlässigen)

b) Lösen Sie die Rekursionsgleichung mit dem Master Theorems.

Problem/Ansatz:

T(n) {  T(2n/3), falls n=1 }

       {   T(n/3), falls n=0   }

Ist mein Gedankengang hier richtig?

b)

Ich bin bei a verunsichert da die Rekursionsgleichung nun eigentlich die Form :{T(n)=aT(n/b)+f(n)} annehmen müsste für den Master theorems.

Comments

2      then return

Hier wird nichts ausgegeben und das Programm endet.

3 if LINALG(n)

4      then REKALG (⌊2n/3⌋)

5      else REKLAG(⌈n/3⌉)

Hier wird auf jeden Fall nochmals REKALG aufgerufen.

Sobald n klein genug ist, erfolgt der Aufruf von REKALG mit n=0 und das Programm endet vielleicht gar nie. (Oder?)

Tipp: Probiere das, wie vorgeschlagen mit verschiedenen Werten von n einfach mal aus.

---

da  then ausgeführt wird werden die Ergbenisse abgerundet, also wenn n= 2

2*2/3 = 1,3333 = 1

wird dann nicht der algorithmus beendet, weil er wieder oben geginnt ?

---

oder wird der LINALG bei n= 0 auf ewig die else anweisug ausführen was immerwieder auf n= 0 schließt und endet somit niemals?

---

Sollst du nicht schauen, wie lang das Programm braucht?

Was macht "return" genau? Das Programm scheint an dieser Stelle zu enden oder allenfalls irgendwohin zu springen. 

Tipp: Probiere das, wie vorgeschlagen mit verschiedenen Werten von n einfach mal aus und zähle die Schritte.

---

mein Lösungsweg :

n= 1

REKALG beendet

n=2

LINALG then -> 2*2/3 gerundet auf 1

n=1

REKALG beendet

n=3

LINALG then -> 2*3/3 gerundet auf 2

n=2

LINALG then -> 2*2/3 gerundet auf 1
n=1

REKALG beendet

n=4

LINALG then -> 2*4/3 gerundet auf n=2

n=2

LINALG then -> 2*2/3 gerundet auf 1
n=1

REKALG beendet

n=5 ...

Wenn n = 3 dann wären es 6 schritte die der algorithmus macht.

---

ab n=2 werden es bei jedem +n 3 schritte mehr.

---

... ob mein Gedankengang bei einsetzen von n in den algortihmus so richtig ist'?

n =1

REKLAG Alg. beendet

n=2

LINALG(2)

then 2*2/3 = Abgerundet 1

dann springt der algortihums wieder zur ersten schleife REKALG wo der algortihmus dann wieder beendet wird oder bleibt man in der schleife und LINALG (2) wird mit n=1 geprüft und dann folgt die else 1/3 aufgerundet zu 1 und das dann endlos ?

Nein - endlos ist es dann nicht, da mit \(n=1\) der Algo REKALG sofort wieder verlassen wird.

Ich habe bei Wiki gelesen, dass eine Rekursion für so ein Problem so aussehen kann:$$T(n) = a \cdot T\left( \frac nb \right) + f(n)$$In Deinem Fall ist \(f(n) \propto n\)- also proportional zu \(n\) - das ist die Funktion LINALG, und das \(b\) wäre doch \(b=\frac 32\), weil dies zu dem größeren Wert von \(T(n)\) führt. Da nur die maximale(!) Anzahl betrachtet wird, kann der Zweig

else REKLAG(⌈n/3⌉)

vernachlässigt werden. Es bleibt$$T(n) = a \cdot T\left( \frac {2n}3 \right) + c\cdot n$$\(a\) und \(c\) sind Konstanten.

---

T(n)=a⋅T(n/b)+f(n)
das ist die Grundform die ich für die Master- Theorems brauche!:)

haben a und c denselben wert? Ich weiß das a  die Anzahl der unterprobleme in der Rekursion sind aber was c sein soll ist mir unklar.

Vielen Dank!

Answer 1

T(n) {  T(2n/3), falls n=1 }

      {  T(n/3), falls n=0  }

Ist mein Gedankengang hier richtig?

Nein $$\left \lfloor \frac {2 \cdot 1}3 \right \rfloor = 0, \quad \left\lceil \frac {1}3 \right\rceil = 1$$siehe auch Gaußklammer. \(n\) sollte in REKALG besser auf \(n \le 1\) geprüft. Sonst gibt es tatsächlich eine Endlosschleife!

Anbei eine kleine Tabelle$$\begin{array}{r|rr}n& \left\lfloor \frac{2n}{3} \right\rfloor& \left\lceil \frac n3 \right\rceil \\ \hline 1& 0& 1\\ 2& 1& 1\\ 3& 2& 1\\ 4& 2& 2\\ 5& 3& 2\\ 6& 4& 2\\ 7& 4& 3\\ 8& 5& 3\\ 9& 6& 3\end{array}$$

Comments

Also  bei n=4 würde der algorithmus so verlaufen =

if LINALG (4)

then (2*4)/3

 = 2

n=2

und nun wird LINALG (4) erneut geprüft aber diesmla wird die else anweisung ausgeführt da n nicht 4 ist sondern 2=

else 2/3

= 1

Alg. beendet  ?

---

... was c sein soll ist mir unklar.

mir auch. Das kommt drauf an, was in LINALG passiert. Das ist nachher aber auch nicht wichtig, soweit ich weiß!

Es soll ja nur die Komplexität des Algorithmus bestimmt werden. Also z.B. ob es \(O(n \cdot \log n)\) oder \(O(n^2)\) oder so ist. Dafür ist die Größe des Faktors irrelevant.

---

Also berechne ich die Fälle ohne c?

Quasi :

Fall 1 n  E O(n ^logb(a-e),e>0

Fall 2 n E O (n^logb(a)

.. oh und muss ich dann für a und b die hälfte nehmen da 2n/3 ?

---

Ich habe ein Rechenweg gefunden der so oder so ähnlich geht:

für T(1)

2(2+1/3)=4/3 >1

also T(n) E O(mit strich drin) (n)

mit a= ln2/ln3=log3(2) = ung.0,63

ist das richtig?

---

ist das richtig?

keine Ahnung! So weit ich das sehe, entspricht Dein Problem in etwa dem, was als 'Fall 2' im Wiki beschrieben ist. Am Ende spielt das \(c\) anscheinend keine Rolle. Aber diese Tabelle ist für mich nicht wirklich logisch! Es ist nicht erklärt, wo das \(\epsilon\) herkommt und auch unklar, ob mit \(a\) und \(b\) immer die gleichen Größen gemeint siond.

Hast Du dazu Unterlagen - ich nehme mal an, Du studierst.

Gruß Werner