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
Sieh Dir die kompakte Form der geometrischen Reihe an. Mehr wirst Du wohl hier nicht erfahren... Hausaufgaben sollst schließlich alleine machen...
>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:
*: http://de.wikipedia.org/wiki/Der_kleine_Gau%C3%9F
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
Ganz einfach: Deine Funktion fuehrt folgende Operation aus:
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.
Ich danke für die ganzen Beiträge nd für die Hilfe ;) Nun les ich mir mal die ganzen Links durch
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
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.