Hallo,

muß man, um die Kosten nach dem uniformen Maß anzugeben, einfach die Anzahl der aufgeschriebenen Befehle bzw. die ANzahl der max. benutzten Register zählen??
(z.B. benutze ich 10 Befehle und 3 Register, also ZeitKosten = 10 und Platzkosten= 3)

Und dann zu dem log. Maß: Muß man hier dann für alle 10 Schritte eine Summe bilden, wie etwa Zeitkosten = l(c(0)) + l(i) + l(input) + l(i) + . . . .
und wie funktioniert das für die Platzkosten?
Platzkosten = Summe l(i) für 0 <= i <= 3

Bitte höflichst um Hilfe/Bemerkungen! Danke!

uniform:
Anzahl der aufgeschriebenen Befehle wär langweilig,
das ist ja immer endlich, und von der Eingabe unabhängig

nene, Anzahl der ausgeführten Befehle beim Programmablauf,
(also ne Schätzung, siehe Beispiel im Skript n^n
(falls es das gleiche wie letztes Jahr ist),
Eingabe ist n, und dann gibts ne while-Schleife
die n-mal ausgeführt wird -> irgendwas * n Schritte -> O(n))

bei Platz ist es dann so einfach ja, wenn 3 dann 3,
in der O-Notation sagt man trotzdem O(1) glaub ich,
O(1) heißt praktisch konstante Anzahl

logarithmisch:
ja im Grunde schon Summe bilden über alle Befehle,

aber man kann sich das normalerweise vereinfachen,
Beispiel n^n: da gibts ja die Schleife mit den Befehlen die n mal ausgeführt werden,
dann brauch man die wenigen Befehle drumherum nicht mehr anschauen,
die in der Schleife machen die Komplexität aus,
und darin findet man wenn man Glück hat einen dominierenden Befehl
(zum Beispiel im n^n-Programm, viel mehr Programme kenn ich nicht ;) ),
so dass man den Rest wieder wegen Minder- oder Gleichwertigkeit nicht betrachten muss
(doppelte Anzahl ist egal, O(2n) = O(n)),
die Kosten dieses wichtigen Befehls also aufsummieren


Platzkosten:
Summe aller maximalen Belegungen aller Register + Adressen,

also wenn i die Nummer des Registers ist:
Summe l(i) + c(l(i)) für 0 <= i <= 3
wobei bei konstanter Anzahl an Registern
wieder die Betrachtung des 'vollsten' Registers reicht,