Komplexitätsklasse

Neue Frage »

Auf diesen Beitrag antworten »
Manuel 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)
 
Auf diesen Beitrag antworten »
eulerscheZahl

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++;
        }
    }
}
Auf diesen Beitrag antworten »
Gast

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.
Auf diesen Beitrag antworten »
eulerscheZahl

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).
 
Auf diesen Beitrag antworten »
Manuel

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.
Auf diesen Beitrag antworten »
eulerscheZahl

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.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »