Aufgabe 4.4 Eingangsarray verändern?

[system]

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

[tyr]

Aufgabe 4.4 Eingangsarray verändern?
Hey, die Frage kam im Testfall-Thread auf, aber hat meiner Meinung nach genügend Relevanz für einen eigenen Thread:

Werden die Arrays, die zum Test an die Methode übergeben werden wiederverwendet?
D.h. darf merge das übergebene array verändern?

Ich zitiere mich hier mal selbst aus dem anderen Thread:

@tyr:1415459394

@bor1:1414957877

ein array wieder verwendet werden, wird die Ausgabe nicht mehr korrekt sein, da das wiederverwendte Array, zwar die verschmolzene Stellen hat, aber da es nicht neuangelegt wurde ist die Länge gleich geblieben.

Sollte man allerdings immer neue Arrays verwendet liefert die Ausgabe genau, dass was sie soll.

Was nun ?!

Ich weiß genau da auch nicht weiter?
Wenn man zb den Test, der in Merge.java schon eingebaut ist, einfach kopiert, sodass er 2 mal ausgeführt wird, dann bekommt man 2 verschiedene Ergebenisse…

Mn kann das schon umgehen,aber das legt voraus, dass man versteht, was der Unterschied zwischen diesen beiden Operationen ist:

int [] abc= {1,5,52,24};
int [] xyz= abc;

//ist nicht das selbe wie

int a=5;
int b=a;

aber ist das jetzt verlangt oder nicht ?

[xenexi]

---

Ich kann dir die Frage zwar nicht beantworten, aber das ist an sich auch nicht so wichtig :-p
Folgendes: Wir sollen die Zahlen erst ab dem Index, ab dem wir sie auch verschmelzen sollen, ausgeben. Und dafuer ist keine Modifikation des Arrays noetig.
Weshalb die Frage nicht weiter relavant ist.

[tyr]

---

EDIT: OK hab meinen Denkfehler gefunden, der war woanders…

[Whitespace]

---

@tyr

Wenn man merge rekursiv implementiert, dann muss man ja immer ein verändertes array übergeben.

kann man, muss man aber nicht, da hat xenexi schon recht

[xenexi]

---

Auch wenn du’s schon geloescht hast:
Da du die Methode rekursiv implementierst, wird, sobald du das Array am Anfang klonst, auch in jedem rekursiven Aufruf das Array geklont, nur eben mit weniger Elementen, aber es wird immer nur um eine konstante Anzahl an Elementen verringert, daher weshalb dein merge() ∈ O(n^2).

[Alicen]

---

@xenexi

merge() ∈ O(n^2).

Ich hoffe, merge() ist nicht O(n^2), sondern eher O(n), //Hier stand mal Quatsch. Weg damit!

[xenexi]

---

@Alicen

@xenexi

merge() ∈ O(n^2).

Ich hoffe, merge() ist nicht O(n^2), sondern eher O(n), sonst wäre die ganze Mühe des Divide-And-Conquer umsonst…

Also es ging erstmal darum, das es quadratisch wird, wenn man das Array klont, was man ja nicht machen sollte. Und ja merge ist O(n).
Zudem ich bin jetzt mal der Meinung, dass das ganze kein Divide & Conquer Algorithmus ist. Du musst! naemlich saemtliche Zahlen vergleichen, sodass du sicher sagen kannst, deine Loesung stimmt. Daher bezweifle ich, dass du das ganze effektiv aufteilen kannst, da sich die Teilprobleme gegenseitig beieinflussen wuerden. (womit der Divide-Part fehle)
Nimm beispielsweise {1, 1, 2, 2, 2,4} als eine Eingabe und noch eine andere { 1,2,2,3,4,5}. Wie willst du das generell aufteilen? Bei der Haelfte? Dann gings beim 2. aber du hast beim. 1. ein Problem (ergaebe dann vielleich { 2,2, 4,4} anstatt {2,4,2,4}).

[Alicen]

---

Arks. Ja. Vertan. Ich war bereits bei 5.3, Skylineproblem (Da gibts ja auch ne Merge ;)). Bitte Divide&Conquer vergessen, ist es natürlich nicht!

Wenn du das Array wirklich klonst wird das tatsächlich quadratisch. Was man natürlich ebenso vermeiden sollte.

[xenexi]

---

Hab mir fast gedacht, dass du schon eins weiter bist