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)
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++;
}
}
}
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.
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).
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.
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.
