Callstack zählt nicht als Speicherverbrauch?
nein
Mit welcher Begründung? Das sind zwar nur (theoretische) 2 * 4-8 Byte Rücksprungadresse sowie Aufrufparameter, aber deren Anzahl steigt bei MergeSort logarithmisch mit der Länge der Eingabedaten, sie ist also nicht in O(1). HeapSort kommt im Gegensatz dazu ohne Rekursion aus und hat einen Speicherverbrauch, der echt in O(1) ist, nicht nur unter Vernachlässigung des Callstacks. Der Speicherverbrauch von HeapSort ist deswegen bei großen Eingabelängen durchaus niedriger als der von MergeSort.
MergeSort ist auch iterativ implementierbar, …
jedenfalls das mit der Rekursion und dem Callstack sind technische Details, auf einem anderen Rechner der das anders handhabt könnte das anders aussehen, die spielen für den Algorithmus an sich also keine Rolle. In einer Klausureinsicht hättest du dir den Punkt aber damit zurückverdient
Also das ist im allgemeinen Fall ja wohl mal gelinde gesagt Blödsinn. Zumindest mit Aufrufparametern MUSS im allgemeinen Fall Speicher verwendet werden, vom Rechner völlig unabhängig (über Rücksprungadressen kann man vllt noch streiten). Dieser Speicherverbrauch ist nur dann nicht zwingend notwendig wenn er wegoptimierbar ist, was zur Rettung deines Posts in diesem Fall auch möglich ist, bloß kann das dann der Programmierer auch gleich selbst tun, wie du sagst, Mergesort ist eben auch iterativ implementierbar. D.h. aber keinesfalls dass man den Callstack im ALLGEMEINEN Fall vernachlässigen könnte!
Es gibt tatsächlich sehr trickreiche Merge-Sort-Varianten, die in-situ arbeiten. Das Klassische Standard-Merge-Sort™, das in der Vorlesung gezeigt wurde, braucht aber immer ein Hilfsarray - Heap-Sort dagegen nicht.
Als Bottom-Up-Variante sogar ohne expliziten Stack, ja. Die funktioniert dann aber wieder ein bisschen anders als der Klassische Standard-Merge-Sort™ - und um den iterativ zu implementieren, braucht man einen expliziten Stack, den man nicht einfach so verschweigen kann.
Was genau auf den Aufrufstack gelegt wird, ist in der Tat stark abhängig von der Zielarchitektur. Dass es einen Aufrufstack gibt, ist aber auf jeder Architektur der Fall.
Einzige Ausnahme, wo man wirklich keinen dynamischen Aufrufstack hat, sind winzige exotische Mini-Architekturen, wo bewusst von Compilerseite aus auf die Möglichkeit rekursiver Funktionsaufrufe verzichtet wird.
Das heißt, wenn man sich diesen Thread ausdruckt und damit in die Klausureinsicht geht, kann man ankreuzen was man will <_<
AFAIR, konnte man auf beide Antworten Punkte bekommen mit entsprechender Begründung, sowas kann schon mal vorkommen und nicht nur in AuD (gell Airhardt 
)
Nur dummerweise ist bei Ankreuzfragen in der Regel keine schriftliche Begründung vorgesehen. 
Dafür gibts dann die Einsichtnahme
Welche der folgenden Ausnahmeklassen müssen in der Methodensignatur deklariert werden, falls die Methode eine solche Ausnahme werfen könnte?
MyOwnError extends java.lang.Error
java.io.IOException extends java.lang.Exception
java.lang.ClassNotFountException extends java.lang.Exception
java.lang.RuntimeException extends java.lang.Exception
Da wir mit Error wenig zu tun hatten, zählen in diesem Fall Errors zu Ausnahmen? Sind ja zwar beide Unterklassen von Throwable aber ein Error ist ja keine Exception.
Sprich korrekt ist ClassNotFountException und IOException?
… hab das gleiche.
Google hat ergeben, dass die Aufgabensteller anscheinend auf der Unterschied zwischen checked und unchecked Ausnahmen rauswollen.
checked: Ausnahmen mit denen der Code umgehen können muss, also catchen oder anderweitig deligieren
unchecked: meist Fehler in der Programmlogik. Können zu Laufzeiten nicht behandelt werden (…)
unchecked sind Errors und RuntimeExceptions sowie deren Unterklassen.
K was hast du bei
a + an + an^2 + … + a*n^b in O(n^b)
Stimmt das?
bin da inzwischen etwas durcheinenader, da ja 1+2+3…+n auch in n² ist
[quote=ri31hoky]
K was hast du bei
a + an + an^2 + … + a*n^b in O(n^b)
Stimmt das?
bin da inzwischen etwas durcheinenader, da ja 1+2+3…+n auch in n² ist
[/quote]O(n^b) ist richtig, weil b der hoechste Exponent ist und du ja nichts anderes als verschiedene Potenzen von n hast.
Ok danke, glaub ich hab den Unterschied zwischen den n damit jetzt verstanden
Mal ne ganz andere Frage:
Ist es ok, wenn wir in der Klausur auf die Klassenbibliothek von Java zugreifen?
Z.B. in der Klausur vom 06.08.2009, Aufgabe 4c). Ziel ist es Radix-Sort zu implementieren, wobei die Methoden Signaturen gegeben waren (nicht aber Klassenname und evntl import-Anweisungen). Wäre es hier ok ArrayList zu verwenden?
[quote=Maddoc]
Mal ne ganz andere Frage:
Ist es ok, wenn wir in der Klausur auf die Klassenbibliothek von Java zugreifen?
Z.B. in der Klausur vom 06.08.2009, Aufgabe 4c). Ziel ist es Radix-Sort zu implementieren, wobei die Methoden Signaturen gegeben waren (nicht aber Klassenname und evntl import-Anweisungen). Wäre es hier ok ArrayList zu verwenden?
[/quote]Keine Ahnung, ob das erlaubt ist (denke schon, war ja auch in den Uebungsaufgaben ok), aber es sollte auch ohne moeglich sein. Sonst stuende da hoechstwahrscheinlich ArrayList statt int[]…
Und man verlangt ja auch nicht von uns, dass wir die API auswendig koennen.
… die ArrayList war ja auch gedacht um die Buckets zu implementieren.
Aber du hast wahrscheinlich recht, irgendwas ist mir bei der Aufgabe durch die Lappen gegangen. Man kann der Methode bestimmt nicht umsonst den Start und Endpunkt im Array mitgeben, aber ich komm nicht drauf wieso. Hat jemand eine Idee?
Habs auch mit Listen und komplett ohne from und to. Würde mich auch interessieren wieso man z.B. nur die Hälfte der Zahlen sortieren will
Edit: seh grad ich hab das from und to sogar eingebaut bei den for-Schleifen, der Sinn erschließt sich mir trotzdem nicht ganz