Hallo!

Ich arbeite grad ein bisschen Vorlesungsstoff nach und bin ein bisschen verwundert über die Definition des logarithmischen Kostenmaßes in Abhängigkeit von der Eingabegröße (zu finden auf Folie 32 dieser Vorlesung (Informatik-Netz)).

Und zwar wird dort erstmal definiert, dass die Größe eines Eingabetupels der Anzahl der Bits entspricht, die man benötigt, um alle Elemente des Tupels darzustellen. Dann definiert er eine Funktion, die dieser Eingabegröße (N) eine natürliche Zahl oder Unendlich zuordnet, und zwar durch: [img]http://mokrates.de/cgi-bin/texstring?T_R(N)%20%3A%3D%20%5Ctext%7Bmax%7D%20%5C%7Bt_R(x)%3A%20n%20%5Cin%20%5Cmathbb%7BN%7D%5Ek%2C%20t_R(n)%20%5Cleq%20N%20%5C%7D[/img]
Gesucht ist also der größte Wert in einer Menge aus lauter t_R(x). Was für ein x das sein soll/darf, steht in der Definition nicht drin. Angenommen, er meinte an der Stelle gar nicht t_R(x), sondern t_R(n), dann macht die Definition wieder wenig Sinn, weil das maximal mögliche Maximum dann N wäre und nicht Unendlich.

Kann mir da irgendwer weiterhelfen? In der Vorlesung hab ich nie die Zeit, mir die Definitionen so genau anzugucken.

Danke!

Hmm, ich glaube, bei der Definition ist etwas durcheinander geraten.

[img]http://mokrates.de/cgi-bin/texstring?T_R(N)[/img] soll eigentlich die maximale Zeit beschreiben, die die RAM R
braucht, um eine Eingabe zu bearbeiten, deren Länge höchstens N ist.

Ich würde also sagen, dass hier gemeint ist
[img]http://mokrates.de/cgi-bin/texstring?T_R(N)%3D%5Cmax%5C%7Bt_R(n)%3A%20n%5Cin%5Cmathbb%7BN%7D%5Ek%2C%20~~%7Cn%7C%5Cle%20N%5C%7D[/img],
wobei [img]http://mokrates.de/cgi-bin/texstring?%7Cn%7C%3A%3D%5Csum_%7Bi%3D1%7D%5Ek%20L(n_i)[/img] für [img]http://mokrates.de/cgi-bin/texstring?n%3D(n_1%2C%5Cldots%2Cn_k)[/img].

Super, das macht Sinn. Dankeschön!

Super, das macht Sinn. Dankeschön!

Die Folienkopieversion in den Webseitenlinks ist heute geändert worden,
auch von mir ein großes Dankeschön!

M. Jantzen

ok, nochmal langsam:
das logarithmische kostenmaß doch quasi die anzahl der bits die für ein/e operation/programm benötigt werden, oder?
im skript sind beispiele gegeben, wobei dann gilt:
"LOAD a " ergibt sich aus L(v(a)), was sich dann aus in abhängigkeit von "a" aus L(i) und/oder L(c(i)) etc. zusammensetzt. Jetzt frage ich mich wie ich das konkrete L(i) bzw. L(c(i)) errechne.
L(i) so definiert:
Die logarithmischen Speicherkosten eines Registers ist die
maximale Länge L(i) aller Zahlen i, die in diesem Register
während des Programmablaufs gespeichert wurden.

aber daraus aknn ich leider nichts konkretes fassen.
Angenommen a = 4, dann ergibt sich für a binär 100. aber wie komme
ich auf die kosten? stehe gerade auf dem schlauch.

Die angegebenen Beispiele beziehen sich auf die Zeitkomplexität. Für die Speicherkomplexität muss man ja nur gucken, wie viele Register überhaupt benutzt wurden und wie viel da jeweils drin gespeichert wurde, maximal.

Aber L(i) ist immer das gleiche: Wenn Du die Binärdarstellung von i hast, nimmst Du einfach die Anzahl benötigter Binärstellen. Also z.B. L(4) = 3, L(127) = 7, L(128) = 8. Allgemein L(i) = floor(ld(i)) + 1.
Für LOAD #4 nimmst Du also einfach L(4) als Zeitkomplexität.
Für LOAD 4 kommt da noch die Länge des Inhalts des 4. Registers drauf - wenn Du den Inhalt nicht kennst, schreib einfach L(c(4)).