Summe von 1 bis n mit Komplexität O(1)

[Jochen (Gast)]

Hallo zusammen!

Ich möchte gerade die folgende Aufgabe lösen, jedoch weiß ich nicht, wie 
das ohne Rekursion bzw. ohne Schleifen funktionieren soll:

Implementieren Sie eine Methode SumPro( int n), die die Summe der 
natürlichen Zahlen zwischen 1 und der natürlichen Zahl n (einschließlich 
der Grenzen) ausgibt und die Komplexität O(1) (in Abhängigkeit von n) 
hat.
Dabei haben die Grundrechenarten, Speicherzugriffe und Vergleiche die 
Komplexität O(1).

Wie soll so etwas funktionieren ??
Danke

[Mathi (Gast)]

Sieh Dir die kompakte Form der geometrischen Reihe an. Mehr wirst Du 
wohl hier nicht erfahren... Hausaufgaben sollst schließlich alleine 
machen...

[6637 (Gast)]

Das gibt irgendwas wie N*(N-1)/2 oder so.

[Mathi (Gast)]

Sorry, nicht geometrische, sondern arithmetische...

[Matthias L. (Gast)]

>die die Summe der
>natürlichen Zahlen zwischen 1 und der natürlichen Zahl n

Klingt nach dem Algorithmus, den sich ein achtjähriger Junge* hat 
einfallen lassen:

$$\sum_{k=1}^n k = 1 + 2 + 3 +...+ n = \frac{n(n+1)}{2}$$

*:
http://de.wikipedia.org/wiki/Der_kleine_Gau%C3%9F

[Markus (Gast)]

Hallo Jochen,

es gibt eine geschlossene Lösung:

sum(n)  =  n*(n+1)/2.


Du kannst z.B. im Bronstein (Formelsammlung, Buch) nachschauen unter dem 
Begriff "Reihe, endliche".

Viele Grüße,
Markus

[Michael G. (linuxgeek)]

Ganz einfach: Deine Funktion fuehrt folgende Operation aus:

$$\sum_{n=1}^{k} n = 1/2 \cdot k^2 + 1/2 \cdot k$$

[Tim T. (tim_taylor)]

Summe=n*(1+(n-1)*0,5));

[Christian (Guest) (Gast)]

Nur so:

Den Algorithmus soll Gauss entwickelt haben als Schüler:

Der Lehrer sagte:
  "alle Zahlen zwischen 1 und 100 addieren"

Gauss war sehr schnell fertig, zur Freude des lehrers ?
  ist mir nicht bekannt, ;-))

[Michael G. (linuxgeek)]

Ja, richtig, das ist der "kleine Gauss"
http://de.wikipedia.org/wiki/Der_kleine_Gau%C3%9F

[Morin (Gast)]

> Dabei haben die Grundrechenarten, Speicherzugriffe und Vergleiche die
> Komplexität O(1).
>
> Wie soll so etwas funktionieren ??

Tja gute Frage... wie baut man einen Computer, der eine Addition in O(1) 
statt O(log n) löst?

Durch die Bedingung n->unendlich aus der O-Notation müsste der doch 
unendlich viele Addiererstellen haben (Binärdarstellung angenommen)...

Und durch die recht übliche Beschränkung n<2^32 ist auch die o.g. 
for-Schleife in O(1) ausgeführt(*), da unabhängig von n nicht länger als 
2^32 mal die Zeit eines Schleifendurchlaufs gebraucht wird...

Solche Aufgaben sind recht oft ein Zeichen, dass der Lehrende selbst 
nicht so ganz genau weiß, was die O-Notation eigentlich ist. Nur mal als 
Warnung, nicht alles blind zu glauben ;)

(*) formal nicht ganz korrekt, da genau genommen sogar die O-Notation 
keinen Sinn mehr macht, wenn man n beschränkt

[Michael G. (linuxgeek)]

O(1) heisst hier, dass der Aufwand konstant ist und nicht in 
Abhaengigkeit von n waechst! O(1) + O(1) + ... + O(1) = 1, in der 
Aufgabenstellung steht ja , dass die Grundrechenarten die Komplexitaet 
O(1) haben...

[Morin (Gast)]

> in der Aufgabenstellung steht ja , dass die Grundrechenarten die Komplexitaet
> O(1) haben...

... und genau das haben sie nicht, genausowenig wie ein 
Sortieralgorithmus O(1) haben kann.

Es ist halt eine "was wäre wenn..." Aufgabe. Wobei man da immer etwas 
vorsichtig sein muss, weil man eben auch falsche Tatsachen korrekt aus 
den falschen Annahmen schlussfolgern kann.

[winne (Gast)]

vielleicht hilft ja das weiter:

http://de.wikipedia.org/wiki/Landau-Notation

Es scheint mir als solle mit dem Hinweis auf die Komplexität O(1) auf 
die Endlichkeit der Funktion verwiesen werden.
Hier scheint es um das prinzipielle Abbild der Funktion zu gehen, und 
nicht um die Unendlichkeit von Werte und Definitionsbereich selbst.

Es handelt sich also meines Erachtens nach darum, die Komplexität so zu 
beschränken das der Aufwand, das vermögen der Maschine nicht 
überschreitet. d.h. der Funktionswert soll mit dem gültigen Alphabet 
darstell-,berechenbar bleiben.

z.B. soll f(x) keinen Wert größer 2^n annehmen wenn "n" die Anzahl der 
binärstellen darstellt.

[Jochen (Gast)]

Ich danke für die ganzen Beiträge nd für die Hilfe ;)
Nun les ich mir mal die ganzen Links durch

[Michael G. (linuxgeek)]

Nei nei nei Winne... da haste was falsch verstanden ;)
Wenn Du die Summe s = n(n+1)/2 berechnest ist der Aufwand uebrigens 
kleiner als bei meiner obigen Formel, hier brauchst Du eine Addition, 
eine Multiplikation und eine Division, Du bist also in der Ordung O(1), 
damit ist die Aufgabe geloest (mit der anderen Formel brauchst Du 3 
Multiplikationen und eine Addition.

Michael

[Detlef _. (detlef_a)]

Michael G. wrote:

> kleiner als bei meiner obigen Formel, hier brauchst Du eine Addition,
> eine Multiplikation und eine Division, Du bist also in der Ordung O(1),
> damit ist die Aufgabe geloest (mit der anderen Formel brauchst Du 3
> Multiplikationen und eine Addition.

3 Multiplikationen und eine Addition wäre auch O(1), 10^6 
Multiplikationen auch, Hauptsache, das hängt nicht von n ab? Oder nich ? 
0(3*5) = O(1) !?

Cheers
Detlef

[Falk B. (falk)]

@ Detlef _a (detlef_a)

>3 Multiplikationen und eine Addition wäre auch O(1), 10^6
>Multiplikationen auch, Hauptsache, das hängt nicht von n ab?

Genau.

Mfg
Falk