Moin,

habe gerade versucht die erste Aufgabe zu lösen und bin sofort an meine Grenzen gestoßen: nämlich in b, da ich nicht weiß, von welchem konstanten Faktor da die Rede ist. Kann mich jemand bitte aufklären? Das wäre sehr nett. Danke.

k/(k+1) ist der konstante Faktor, und die Aufgabe soll
für alle k > 0 gelten. Anders gefragt: wenn k gegen
unendlich strebt, was passiert dann mit k/(k+1).

Mit dem konstanten Faktor ist meiner Meinung nach nicht der Faktor in der Rekursionsgleichung gemeint, sondern der Faktor, der in der O,
[img]http://mokrates.de/cgi-bin/texstring?$%5COmega$[/img] bzw. [img]http://mokrates.de/cgi-bin/texstring?$%5CTheta$[/img] Notation mit der Funktion multipliziert wird. Dieses c verändert sich halt mit unterschiedlichem k und wie diese Beziehung aussieht, ist glaube ich gefragt.

angenommen
[img]http://mokrates.de/cgi-bin/texstring?%5C(T(n)%20%5Cin%20%5Ctheta%20(n)%5C)[/img]
hat man schon gezeigt. dann habe ich ja
[img]http://mokrates.de/cgi-bin/texstring?%5C(T(n)%20=%20c%20%5Cdot%20n%5C)[/img]
aber wie komme ich dann an das k in T(n) ran um es irgendwie mit c in
abhängigkeit zu bringen?

angenommen
[img]http://mokrates.de/cgi-bin/texstring?%5C(T(n)%20%5Cin%20%5Ctheta%20(n)%5C)[/img]
hat man schon gezeigt. dann habe ich ja
[img]http://mokrates.de/cgi-bin/texstring?%5C(T(n)%20%3D%20c%20%5Cdot%20n%5C)[/img]

Das kann man so allgemein nicht sagen, denn z.B.
T(n)=n*sin(n) erfüllt die erste Beziehung auch,
ist aber nicht linear.

Ich kenne allerdings die Aufgaben nicht. Wenn
ihr die mal verlinkt, kann vielleicht jemand
genaueres dazu sagen.

Nabend!
Bei Aufgabe 2 (b) steht geschrieben für GET-ELEMENT(L):
gibt eine beliebige in der Datenstruktur L enthaltene Zahl zurück.

Was soll uns das sagen?
1. Irgendeine Zahl wird zurückgegeben
2. Der Parameter sollte k sein und wir geben eine Zahl zurück, die an der Position k steht, sofern wir denn mit einem Array arbeiten…

Jemand ne Idee?

irgendeine wird zurück gegeben

Nabend!
Bei Aufgabe 2 (b) steht geschrieben für GET-ELEMENT(L):
gibt eine beliebige in der Datenstruktur L enthaltene Zahl zurück.

Was soll uns das sagen?

Wie Du richtig bemerkt hast, hat die Funktion keinen Parameter k, und das ist Absicht. Die Funktion soll einfach ein beliebiges Element zurückliefern, dass zu dem Zeitpunkt aber in der Datenstruktur L enthalten sein muss - und das in konstanter Zeit (also unabhängig von der Maximalgröße n der Menge). Dadurch werden schonmal einige mögliche Datenstrukturen ausgeschlossen.

Ich platz zwar in die Runde rein, aber ne Frage: In Aufgabe zwei wird ja ne Menge L beschrieben. Es steht da L={1…n}, heist es das die Zahlen nicht in Reihenfolge liegen müssen. Das z.B. n = 5 sein kann aber L = {1,4,3,14,5} ??? oder ist das mit Reihenfolge gemeint und das für n=5 L={1,2,3,4,5} genau so ist ???

Danke für euro hilfe.

Ich platz zwar in die Runde rein, aber ne Frage: In Aufgabe zwei wird ja ne Menge L beschrieben. Es steht da L={1…n}, heist es das die Zahlen nicht in Reihenfolge liegen müssen.

L={1…n} steht da eigentlich nicht. Gemeint ist auf jeden Fall: [img]http://mokrates.de/cgi-bin/texstring?%5Cmathbb%7BL%7D%20%5Csubseteq%20%5C%7B1%2C%202%2C%20...%20n%5C%7D[/img]
Das heißt, n wird vorgegeben, und die Datenstruktur soll sich dann für alle Zahlen zwischen 1 und n merken, ob sie in der Datenstruktur enthalten sind oder nicht. Wie Du die Zahlen nun speicherst (ob in einer bestimmten Reihenfolge oder nicht), bleibt Dir überlassen, solange Du die Vorgaben für die Zeitkomplexität dabei einhältst. Beim Aufruf von ADD und REMOVE ist aber auf jeden Fall sichergestellt, dass k <= n, also für n=5 ist L={1,4,3,14,5} kein möglicher "Zustand", wohl aber L={1,2,3,4,5} oder L={4,1}.

ok, ich bin wohl der einzige, der mit 1b probleme hat [img]http://www.fb18.de/gfx/wand.gif[/img]

die substitutionsmethode ist imo im skript auch nicht verständlich.
will ich also in
[img]http://mokrates.de/cgi-bin/texstring?%5C(T(n)=T(cn)+n%5C)[/img] das
T(n) wieder einsetzen, was passiert da dann? setze ich T(n) für n ein? aber
dann bekomme ich ja eine endlose verschachtelung von T(T(T(T(….).
ich begreife das nicht.
die abhängigkeit von c und k mal gar nicht erwähnt, wobei sich das wohl ergibt
wenn man den anderen kram gebastelt hat.

Wenn ich mich nicht irre funktioniert das wiederholte einsetzen so:

T(n) := T(c*n) + n

Wenn du T(5) berechnen willst, dann machst du folgendes:

(a) T(5) = T(c*5)+5 // T(n) mit n=5

Jetzt kennst du das Ergebnis von T(5) noch nicht, weil die Funktion rekursiv definiert ist. D.h. du musst T(c*5) ausrechnen um T(5) berechnen zu können:

(b) T(c*5) = T(c*c*5)+c*5 // T(n) mit n=c*5

Wie man sieht ist dies ähnlich wie bei (a), wobei n=c*5 bei (b).

Da kann man jetzt ja ein schema erkennen.
T(n) wird immer durch T(c*n)+n ersetzt.

Für T(5) sieht es dann so aus:

T(5)
= T(c*5)+5
= T(c*c*5) + c*5 + 5
= T(c*c*c*5) + c*c*5 +c*5 + 5
= …
usw bis die rekursion beendet wird.
Für T(n) muss man einfach nur die 5 durch n ersetzen.