Laufzeit

[virtual12]

Ich soll eine Klasse mit einer quadratischen Methode schreiben, deren Laufzeit auch quadratisch ist. Diese Methode bekommt ein double Array und soll den Abstand der beiden Werte zurückgeben, die sich am nächsten sind. Zum Beispiel also
{1, 2, 5, 7, 9, 11, 15, 21, 56, 23, 26} gibt 1 als kleinsten Abstand. Viele Ideen habe ich noch nicht, aber ich versuche mich mal mit einem kleinen Anfang:

double[] abstand = new double[1000];
for(int i = 0; i<abstand.length; i++) {
for(int j = 0; j<abstand.length; j++) {
Math.abs(abstand[i][j]);
System.out.println(abstand);
}
}

Ist nur ein sehr grober Ansatz. Habt ihr Ideen, wie ich das angehen könnte?

 

[Bitfehler]

Überleg doch mal welche logischen Schritte du machen musst.

1. Wähle eine Zahl aus der vorhandene Menge aus (erste for-Schleife)
2. Wähle eine zweite Zahl aus vorhandenen Menge aus, die ungleich der bereits gewählten ist
3. Berechne den Abstand zwischen den beiden Werten
4. Hier bist du nun dran. Was muss mit dem errechten Abstand gemacht werden?
5. Wieder hole das Vorgehen bis alle Kombinationen durch sind

Nenne das Array mal bitte nicht abstand, das verwirrt nur, da es ja keine Abstände enthält.

 

[stg]

Mit "quadratischer Laufzeit" kann ich ja was anfangen, aber was bitte schön soll denn eine "quadratische Methode" in diesem Zusammenhang sein?

Wie man das Problem in quadratischer Laufzeit lösen kann hat Bitfehler dir ja nun schon skizziert. Das Problem ist aber auch in quasi-linearer Zeit lösbar, falls das für dich eine Rolle spielt.

 

[virtual12]

Okay, würde jetzt so etwas daraus machen:

double[] a = new double[1000];
    public static void naechstesPaarQuad() {
        for(int i = 0; i < a.length; i++) {
            for(int j = 0; j < a.length; j++) {
                if(Math.abs(a[i] - a[j]));
                else
                    Math.abs(a[i] + a[j]);
            }
        }
       
       
    }

Funktioniert aber leider nicht.Was mache ich falsch?

 

[virtual12]

Sorry, das mit der quadratischen Methode war etwas unglücklich formuliert. Da sie eine quadratische Laufzeit ausgibt, werde ich die Methode nachher so nennen.

 

[Bitfehler]

if(Math.abs(a[i] - a[j]));

Magst du mir mal erklären, was das machen soll?

EDIT: Da ist irgendwas verloren gegangen, nun besser

 

[stg]

.Was mache ich falsch?

Wie würdest du das Problem lösen, wenn du nur einen Stift und ein Blatt Papier hättest?
Versuch mal das vorgehen in Worten wiederzugeben. Das schreibt sich der Code danach fast ganz von allein.

 

[virtual12]

wenn ich zum Beispiel diese Zahlen hätte (2.0, 3.0, 5.0, 7.0, 9.0) würde ich der Reihe nach durchgehen und alle Paare miteinander vergleichen, also erst 2.0 mit 3.0 ergibt 1.0, dann 3.0 mit 5.0 ergibt 2.0, dann 5.0 mit 7.0 ergibt 2.0 usw. Dann sieht man ja, dass der geringste Abstand von einem Paar 1.0 ist. Aber ich muss die ganze Reihe durchgehen, weil der geringste Abstand kann ja auch erst bei dem letzten Paar auftreten.

 

[virtual12]

@Bitfehler: mir wurde von jemandem gesagt, ich solle dabei Math.abs benutzen. Das wäre leichter. Vielleicht habe ich mich zu sehr daran gehalten.

 

[stg]

@Bitfehler: mir wurde von jemandem gesagt, ich solle dabei Math.abs benutzen. Das wäre leichter. Vielleicht habe ich mich zu sehr daran gehalten.

Math.abs zu benutzen ist nicht nötig, aber vollkommen in Ordnung (sofern ihr das nutzen dürft)

Die Frage von Bitfehler war aber nicht darauf bezogen, sondern vielmehr darauf, was du mit dem Code-Schnipsel eigentlich ausdrücken willst.
In Worte übersetzt steht da:
"Wenn der Abstand von Zahl1 und Zahl2"
Was soll das nun bedeuten?

 

[virtual12]

Okay, eigentlich wollte ich sagen wenn das der kleinste Abstand ist, soll das ausgegeben werden, sonst soll das nächste Paar verglichen werden. Aber ich sehe gerade, ich muss ja erst die Reihe an Paaren durchgehen, um überhaupt entscheiden zu können, was das Paar mit dem kleinsten Abstand ist. Aber wie kann ich das als Code formulieren?

 

[Meniskusschaden]

Werden die Zahlen in beliebiger Reihenfolge vorgegeben oder sind sie immer sortiert? Im zweiten Beispiel sind sie sortiert (2.0, 3.0, 5.0, 7.0, 9.0) und im ersten fast (die 56 könnte ja ein Versehen sein) {1, 2, 5, 7, 9, 11, 15, 21, 56, 23, 26}.

 

[virtual12]

Die Zahlen werden in beliebiger Reihenfolge vorgegeben. Das oben war Zufall, dass es schon sortiert ist.

 

[Meniskusschaden]

Welche Lösung würde dein Ansatz denn bei dem Beispiel (2.0, 6.0, 9.0, 3.0 12.0) berechnen?

 

[virtual12]

ich vermute mal, mein Ansatz würde nur die ersten beiden vergleichen und 4.0 ausgeben, was falsch ist

 

[Meniskusschaden]

Ich meinte eigentlich diesen Ansatz:

wenn ich zum Beispiel diese Zahlen hätte (2.0, 3.0, 5.0, 7.0, 9.0) würde ich der Reihe nach durchgehen und alle Paare miteinander vergleichen, also erst 2.0 mit 3.0 ergibt 1.0, dann 3.0 mit 5.0 ergibt 2.0, dann 5.0 mit 7.0 ergibt 2.0 usw. Dann sieht man ja, dass der geringste Abstand von einem Paar 1.0 ist. Aber ich muss die ganze Reihe durchgehen, weil der geringste Abstand kann ja auch erst bei dem letzten Paar auftreten.

 

[virtual12]

Dann 3.0 als Ausgabe

 

[Meniskusschaden]

Der Abstand zwischen dem ersten und vierten Element im Beispiel (2.0, 6.0, 9.0, 3.0, 12.0) ist aber nur 1.0.

 

[virtual12]

ich soll nur die unmittelbar nebeneinander liegenden vergleichen

 

[Meniskusschaden]

Wirklich? Warum soll die Laufzeit denn dann quadratisch sein? So mußt du es ja mit Vorsatz ineffizient gestalten.

 

[virtual12]

Ja, und wie geht das?

 

[Meniskusschaden]

Falls du n Zahlen hast, ermittelst du die Lösung einfach nach deinem Ansatz und durchläufst anschliessend oder vorher noch n^2 Mal eine Schleife, die bei jeder Iteration irgendetwas Überflüssiges mit konstanter Laufzeit tut. Bezweifle aber stark, dass es wirklich so gedacht ist.

 

[Bitfehler]

wenn ich zum Beispiel diese Zahlen hätte (2.0, 3.0, 5.0, 7.0, 9.0) würde ich der Reihe nach durchgehen und alle Paare miteinander vergleichen, also erst 2.0 mit 3.0 ergibt 1.0, dann 3.0 mit 5.0 ergibt 2.0, dann 5.0 mit 7.0 ergibt 2.0 usw. Dann sieht man ja, dass der geringste Abstand von einem Paar 1.0 ist. Aber ich muss die ganze Reihe durchgehen, weil der geringste Abstand kann ja auch erst bei dem letzten Paar auftreten.

Genauso und nun machst du das im Code.
Und hast eine Variable, in der du die kürzeste Distanz speicherst. Bei deinem Verglich zweier Werte kommt ein Abstand heraus. Diesen Abstand vergleichst du dann mit dem bereits vorhandenen Abstand. Ist der neue kleiner als der alte, dann ist der neue Abstand der aktuell kürzeste. Wenn nicht, dann vergleich die nächsten Werte. Am Ende hast du dann den kürzesten Abstand.

Dabei ist es denn egal, ob das Array sortiert ist oder nicht. Eine Kleinigkeit musst du dabei aber beachten, das wirst du dann aber schon herausfinden.

 

[JStein52]

So mußt du es ja mit Vorsatz ineffizient gestalten.

Verstehe ich dann auch nicht. Du hast doch dann nur eine Schleife in der du das i.te Element mit dem i+1.ten vergleichen musst ???