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
>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:
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
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, ;-))
> 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
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...
> 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.
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.
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
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
@ 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
