# komplexität bestimmen



## ficak (21. Jan 2011)

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 (21. Jan 2011)

Was meinst du mit Komplexität?


----------



## SlaterB (21. Jan 2011)

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 (21. Jan 2011)

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 (21. Jan 2011)

die laufzeit


----------



## Landei (21. Jan 2011)

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 (21. Jan 2011)

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 (21. Jan 2011)

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 (21. Jan 2011)

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 (21. Jan 2011)

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 (21. Jan 2011)

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.


----------

