---

Geschrieben von Manuel am 03.05.2018 um 16:52:

  Komplexitätsklasse

Meine Frage:
Hallo zusammen,
ich hätte mal eine Frage und zwar habe ich hier eine Aufgabe und ich weiß absolut nicht welche Komplexität besitzt.
Java-Code:
int sum2(int n){
return n*(n+1)/2;
}
sum2: O(?)

Meine Ideen:
Hab echt rum probiert aber weiß es nicht. Hab mir gedacht vielleicht O(n^3)

---

Geschrieben von eulerscheZahl am 03.05.2018 um 21:29:

 

Für den Computer macht es keinen Unterschied, ob du 1+2 rechnest, oder 23421+53732.
Du hast hier 3 Rechenschritte(+, *, /). Die Anzahl ist immer gleich, unabhängig vom n, deshalb konstante Laufzeit O(1).

O(n^3) wäre sowas:

code: 1: 2: 3: 4: 5: 6: 7: 8: int x = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { x++; } } }

---

Geschrieben von Gast am 05.05.2018 um 12:55:

 

Hallo e,

O(1) verstehe ich nicht. Ich muss doch eine Multiplikation n*n ausführen, also mit Schulmethode O(n^2). Die Laufzeit der Multiplikation ist abhängig von der Größe des n, wenn man mal die Begrenzung des Integers außer Acht lässt.

---

Geschrieben von eulerscheZahl am 05.05.2018 um 14:35:

 

Dein Code verwendet aber ein Integer.
Und für diesen Datentyp ist die Multiplikation in der Laufzeit konstant.

So wie ich die Multiplikation in der Schule gelernt habe, geht sie übrigens in O(log(n)).
O(n^2) würde je bedeuten, dass du n^2 mal in Einerschritten hochzählst, bis du das Ergebnis erreichst. Ich glaube nicht, dass das so gelehrt wird.
An O(n) kann ich mich noch erinnern (also durch wiederholte Addition: n+n+n+n....+n).

---

Geschrieben von Manuel am 05.05.2018 um 16:47:

 

Hallo eulerscheZahl,
danke für die schnelle Antwort. Was meinst du mit die Anzahl ist gleich? Woran sieht man das? #Gast O(n^2) hatte jmd als Lösung in der Uni und der Prof meinte es wäre falsch.

---

Geschrieben von eulerscheZahl am 07.05.2018 um 20:35:

 

Es gibt immer 3 Rechnungen, die durchgeführt werden müssen: eine Multiplikation, eine Addition und eine Division. Das ist fest und hängt nicht von n ab (etwa: n viele Additionen oder n^2 viele). Deshalb konstante Laufzeit.