komplexität bestimmen

[ficak]

hi leute. ich muss die komplexität der folgenden codes bestimmen. bin mir dabei aber sehr unsicher. würde mich freuen wenn mir jemand sagen könnte wie ich das schneller erkenne oder irgendwie bestimme. für die beiden code habe ich mir gedacht
1) konstante fkt
2)hier verwirrt mich das b

wenn mir irgendwer helfen könnte wäre sehr dankbar

1)

 public static boolean dupe1(int[] a) {
for (int i=0;i<a.length;i++)
for (int j=0;j<a.length;j++)
if (a[i] == a[j] && i != j) return true;
return false;
}

2)

public static boolean dupe2(int[] a) {
boolean b = false;
for (int i=0;i<a.length;i++)
for (int j=0;j<a.length;j++)
if (a[i] == a[j] && i != j) b = true;
return b;
}

 

[XHelp]

Was meinst du mit Komplexität?

 

[SlaterB]

beim zweiten wird b zwar evt. geändert, das hat aber keinen Einfluss auf die Arbeit der Methode,
etwa die Anzahl der Vergleiche, b kannst du ignorieren,
edit: obwohl es schon interessant was die erste Funktion dagegen anders macht..

zu 1) schreibe doch, warum du das vermutest,
welche Komplexitäten kennst du, welche Regeln dazu, wann ist deiner Meinung nach etwas von Komplexität x, wann y, wann z,
wieso sollte 1) gerade konstant sein und nicht etwas anderes (was gibt es noch anderes)?

 

[ficak]

also ich soll die laufzeit bestimmen. dafür muss ich ja wissen welche fkt der code darstellt
bei der 1 dachte ich es wäre konstant weil das dingen wahr wird wenn j ungleich i ist und bzw aber a gleich a[j] sein soll. sonst ist das false. und mir ist da nur konst fkt eingefallen. ehrlich gesagt ist das ja wohl nicht die beste mehtode zur bestimmung. ich soll die beiden codes vergleichen und sagen ob sie gleiche komp haben. ich habe das so erklärt bekommen das ich die fkt bestimmen muss und dann gucken ob un dwleches schneller wächst

 

[ficak]

die laufzeit

 

[Landei]

Variante 1) hat eine Worst-Case-Komplexität von O(n²), wobei n hier a.length ist. Der "schlechtestmögliche" Fall ist natürlich, dass das Array keine doppelten Elemente enthält. Im besten Fall ist die Komplexität O(1) (wenn gleich der erste Vergleich ein Treffer ist). Für die durchschnittliche Komplexität müsste man die Werteverteilung kennen.

Variante 2) hat unabhängig vom Input (also auch im besten, durchschnittlichen und schlechtesten Fall) immer O(n²).

 

[ficak]

danke kannste mir auch erklären wie genau ich das sehe?
also bei dem ersten wäre ich jetzt auf o(n^2)nicht gekommen.
das zweite weiß ich jetzt nicht genau warum es immer O(n^2) ist

 

[XHelp]

Ich denke die Aufgabe zielt darauf aus, die verschiedenen Landau-Symbole zu verwenden:
Beim 1. wäre das ja O(n²), und beim 2.:

 

[ficak]

danke für die lösung. aber ich hätte doch gerne eine erklärung wie man darauf kommt. bis habe ich immer richtig oder halbwegs richitg geraten aber so kann man ja nicht durch java gehen

 

[XHelp]

wie du auf n² kommst, müsste ziemlich offensichtlich sein. Äußere Schleife läuft n mal und die innere Schleife läuft n mal, also n²
Beim 1. Beispiel kann es passieren, dass du vorzeitig die Schleifen beendest (durch return), also läuft der Algo "höhstens" n² Schritte
Beim 2. Beispiel läufst du immer die ganzen Schleifen ab und gibst erst dann das Ergebnis zurück. Also läufst du da immer "genau" n² Schritte

 

[ficak]

danke danke danke..nur in paar sätzen hast du mir das erklärt und ich meine es verstanden zu haben. ich bin das wohl voll falsch angegangen und es war zufällig richtig.