Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Komplexitätsklasse » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Komplexitätsklasse
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Manuel
unregistriert
Komplexitätsklasse Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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)
03.05.2018 16:52
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.855

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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


__________________
Syntax Highlighting fürs Board (Link)
03.05.2018 21:29 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Gast
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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.
05.05.2018 12:55
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.855

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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).

__________________
Syntax Highlighting fürs Board (Link)
05.05.2018 14:35 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Manuel
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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.
05.05.2018 16:47
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.855

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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.

__________________
Syntax Highlighting fürs Board (Link)
07.05.2018 20:35 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Komplexitätsklasse