www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Summe von 1 bis n mit Komplexität O(1)


Autor: Jochen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Mathi (Gast)
Datum:

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

Autor: 6637 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das gibt irgendwas wie N*(N-1)/2 oder so.

Autor: Mathi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sorry, nicht geometrische, sondern arithmetische...

Autor: Matthias Lipinsky (lippy)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Michael G. (linuxgeek) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ganz einfach: Deine Funktion fuehrt folgende Operation aus:

Autor: Tim T. (tim_taylor)
Datum:

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

Autor: Christian (Guest) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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, ;-))

Autor: Michael G. (linuxgeek) Benutzerseite
Datum:

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

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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

Autor: Michael G. (linuxgeek) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: winne (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jochen (Gast)
Datum:

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

Autor: Michael G. (linuxgeek) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ 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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.