Summenformel vs. For-Schleife

[WarSlash]

Hallo zusammen,

ich bin etwas verwirrt. Folgender Sachverhalt:
Es gibt ja diese Summenformel. Diese hat ja O(n^2) als O-Notation:

http://666kb.com/i/b9ixsa04jrebkvx3d.gif

Zu dieser Funktion möchte ich auch die O-Notation ermitteln:
http://666kb.com/i/b9ixtwnnfvqkgaukp.gif

Da kann man ja sehen, dass hier alles n-Mal geprüft. bzw n-Mal Daten verschoben werden. Man soll für diese Analyse ja nur die wirklich relevante Teile des Codes betrachten.

Also wäre das hier O(n), weil hier nur eine Schleife läuft und nur n-mal etwas geprüft und verschoben wird.

Aber steht das nicht in Konflikt mit der Abschätzung zur Summenformel?
Die Summenformel hat durch die Formel oben hat ja O(n^2). Aber programmtechnisch müsste das doch O(n) sein, da ich ja von 0 bis n durchzähle.

Mathematisch ist ganz klar, es muss O(n^2) gelten.
Wegen den der Addition soll dieses wohl gelten oder wie?

Wenn dem so ist, muss die Funktion da oben doch auch O(n^2) haben.

Sei a = 0
for(i=0; i<n;i++)
a++;

Also ist das hier O(n^2), wegen der Summenformel?! Sieht für mich einfach nach O(n) aus. Weil ich ja nur 1 Schleife habe.

for(i=0; i<n;i++) for(j=i; j<n;j++) {
for(k=i; k<=j;k++)
a++

Und das ist dann O(n^3)? Aber wirkt durch die Summenformel-Regel wie O(n^4)

[samm]

Hallo zusammen,

ich bin etwas verwirrt. Folgender Sachverhalt:
Es gibt ja diese Summenformel. Diese hat ja O(n^2) als O-Notation:

http://666kb.com/i/b9ixsa04jrebkvx3d.gif
Ich glaube, das ist ein Überlegungsfehler ;): Nur weil etwas ein Ergebnis hat, das n^2 beinhaltet, ist der Aufwand noch nicht O(n^2). Die Formel hier ist das gleiche wie
a = 0;
for(i=1;i<=n;i++)
a += i;und ebenso O(n) im Aufwand.

[WarSlash]

Mich wunderte es nur, weil ich mal mathematische Formel abschätzen musste. Und wenn ich die programmieren würde, dann ist die Summenformel einfach O(n) für den Rechner.

Ich glaube ich habe mathematisches Abschätzen mit programmtechnischen Abschätzen durcheinander geworfen?!

[Expandable]

Anstatt 1+2+3+4+...+n auszurechnen, kannst du auch einfach gleich n(n+1)/2 ausrechnen. Dazwischen steht ein "=", wie man leicht zeigt. Also hat die Summenformel entweder O(1), wenn du n(n+1)/2 ausrechnest, oder O(n), wenn du 1+2+...+n ausrechnest.

n(n+1)/2 ist der WERT der Formel, nicht die Laufzeit!

[wry]

@Expandable
Ich hab dazu eine Frage. Ich glaube ich verstehe deine Erklärung:
Bei der Summe (1+2+..+n) wächst mit dem n, die Anzahl der Operationen linear mit, folglich O(n).
Bei der Formel hingegen bleibt die Anzahl der Operationen mit wachsendem n konstant (1 Addition, 1 Multiplikation, 1 Division), deshalb O(1).

Meine Frage:
Hängt das aber nicht davon ab, wie ich die "atomaren Operationen" definiere? Wenn ich die Multiplikation z.b. nicht als 1 atormare Operation betrachte, sondern als eine Sammlung von Additionen, dann würde das O(1) nicht mehr stimmen, oder?

z.b. 8 * 3 = 8+8+8
Generell (Konstante * n) => n Additionen => O(n)
Wenn ich also die Multiplikation so sehe, dann wäre die Multiplikation selbst schon O(n) und die Formel nicht mehr O(1)

[Dr.Doom]

Du darfst das nicht "zu mathematisch" sehen, da eine Multiplikation *2, *4... auch durch Shifts schnell durchgeführt werden können.

Stell' dir einfach vor, dass irgendwas n-mal gemacht werden muss, also n Arbeitschritte, dann hat man O(n).

Muss man zusätzlich zu diesem variablen n irgendwas, aber mit einer bekannten, festen Anzahl machen, zB 5 mal, dann hätte man O(5*n).
Da aber für "verdammt gigantische n" die 5 Arbeitschritte uninteressant sind, kann man Konstanten weglassen.

Muss man hingegen bei jedem der n Arbeitsschritte jeweils m (variabel!) zusätzliche Arbeitschritte machen, dann hat man O(n*m). Falls zufällig n=m, dann halt O(n²).

[wry]

@Dr.Doom
In seinem Beispiel, also bei der Formel [ n*(n+1) ]/ 2, ist das ja aber nicht der Fall, dass bei der Multiplikation die Anzahl der Operationen konstant/vernachlässigbar bleibt. Vorausgesetzt man multipliziert durch wiederholte Addition, sprich wir nehmen jetzt einfach an, dass Multiplikation eine wiederholte Addition ist.

In seinem Beispiel wären dann folgende Multiplikation mit Komplexität O(n):

n*(n+1) => Die Variable n wird n+1 mal mit sich selbst addiert => Die Anzahl der Additionen wächst linear mit dem n mit => O(n)

?

[Senior Sanchez]

Multiplizierst du selber im Kopf in dem du immer wieder das gleiche drauf addierst?
Nein, sicherlich nicht.

Warum forderst du es dann für diese Betrachtung? Eine Multiplikation ist dermaßen elementar, dass passiert in konstanter Zeit, sofern wir hier nicht von richtig abgefahrenen Operationen ausgehen (Multiplikationen von Zahlen mit 10.000 Stellen oder so).

Man kann nahezu jede mathematische Operation ungleich aufwändiger machen.
Wieso erlaubst du zum Beispiel eine direkte Addition von n+1 mit sich selbst? Das könnte man auch als Schleife auffassen, bei der für jedes n+1 n+1 mal in einer Schleife 1 dazu addiert wird.

Du siehst, es macht keinen Sinn selbst solche einfachen Operationen komplizierter zu machen als sie sind.

In der O-Notation, die eh nur eine mehr oder minder schlechte Abschätzung ist, geht es nur um aufwändige Operationen.

[Neomi]

Vorausgesetzt man multipliziert durch wiederholte Addition, sprich wir nehmen jetzt einfach an, dass Multiplikation eine wiederholte Addition ist.

Und wenn man auch noch vorraussetzt, daß eine Addition nur ein wiederholtes Inkrementieren um 1 ist, dann hat schon die Addition eine lineare Laufzeit, die Multiplikation entsprechend eine quadratische. Warum geht ihr (WarSlash und wry) also von konstanter Laufzeit bei der Addition aus? Wohl aus gutem Grund, weil wiederholtes Inkrementieren weder theoretisch noch praktisch sinnvoll ist. Bei der Multiplikation sieht es aber genauso aus, wiederholtes Addieren ist weder theoretisch noch praktisch sinnvoll. Es mag Architekturen geben, bei denen die Multiplikation keine (zumindest grob) konstante Laufzeit hat, aber die sind dann eher die Ausnahme.

Edit: aha, gleicher Gedanke mit ein paar Sekunden Latenz. :D

[wry]

Ich hab dabei z.b. an einen konkreten Prozessor gedacht, wo z.b. die Addition eine elementare Operation darstellt. Die Multiplikation hingegen auf der Addition aufbaut. Ok, ich kenn mich bei Prozessoren nicht wirklich aus, deswegen könnte der Gedanke blödsinn sein :redface:

Mir ist das so in den Sinn gekommen, und ich dachte, dass der Threadstarter, das vielleicht auch so aufgefasst haben könnte.

[Monger]

Also, nur falls es noch nicht deutlich genug geworden ist: das O-Kalkül hat absolut NICHTS mit mathematischen Formeln zu tun!

Das O Kalkül betrachtet lediglich den Algorithmus, der vielleicht versucht eine Formel in etwas rechnerverträgliches umzusetzen.

Simples Beispiel: x = m/n

Das O-Kalkül dafür? Keine Ahnung! Kommt auf den Algorithmus an. Wenn m durch n ganzteilig teilbar ist, sind wir innerhalb von einem Schritt durch. Oder genauer: wenn m durch n eine ganzteilige Potenz von 2 ist. Andernfalls haben wir möglicherweise eine Menge von Nachkommastellen. Die Errechnung von jeder weiteren Nachkommastelle frisst Zeit - wir müssen uns also überlegen was für eine Genauigkeit wir eigentlich erreichen wollen.

In der Realität wird man in aller Regel eine genormte Genauigkeit annehmen. Und da jede aktuelle CPU eine dedizierte Einheit für Gleitkommaberechnungen hat, wird das letztendlich auch in O(1) umsetzbar sein.

Das O-Kalkül hängt also ganz von dem verwendeten Algorithmus ab - und von den Randbedingungen auf die der Algorithmus aufsetzt. Das hat einzig und allein Relevanz für die Informatik, und für sonst nichts.

[wry]

Das O-Kalkül hängt also ganz von dem verwendeten Algorithmus ab - und von den Randbedingungen auf die der Algorithmus aufsetzt. Das hat einzig und allein Relevanz für die Informatik, und für sonst nichts.
Genau das hat mich gewundert. Ich hab das Post von Expandable so aufgefasst, dass er implitzit einen Algorithmus angenommen hat wo, alle Operationen atomar sind. Jetzt ist mir das mit dem O wieder ein bisschen klarer geworden :smile:

[Pinoccio]

Aber steht das nicht in Konflikt mit der Abschätzung zur Summenformel?Nein. So wie man in einem roten Bus auch schwarzfahren kann, so steht die Berechnungskomplexität (hier O(n)) in keinem Zusammenhang mit dem Ergebnis der Summe (hier O(n^2)), auch wenn beides Groß-O heißt.Ich glaube ich habe mathematisches Abschätzen mit programmtechnischen Abschätzen durcheinander geworfen?!Exakt.

Sieht für mich einfach nach O(n) aus. Weil ich ja nur 1 Schleife habe.Dieser Schluß ist - für den Anfang - eine gute Idee. Allgemein gilt: Anzahl der Schleifendurchläufe * Aufwand in der Schleife = Gesamtaufwand (bezogen auf die Zeit).
Meine Frage:
Hängt das aber nicht davon ab, wie ich die "atomaren Operationen" definiere?Natürlich.
Und wenn man auch noch vorraussetzt, daß eine Addition nur ein wiederholtes Inkrementieren um 1 ist, dann hat schon die Addition eine lineare LaufzeitNein, da die Addition +1 im binären einen Übertrag jedes einzelnen Bits hervorrufen kann ist die Addition +1 im schlimstem Fall O(log(n)). Addition im Allgemeinen als O(n*log(n)). (Krümelkackerei)
Es mag Architekturen geben, bei denen die Multiplikation keine (zumindest grob) konstante Laufzeit hat, aber die sind dann eher die Ausnahme.Normalerweise 1 Operation = 1 Takt. Intern natürlich nicht, die Rechenwerke arbeiten schneller, müssne ja auch mehrere Schritte machen.
Es gibt/gab aber afaik tatsächlich Architekturen, wo Zahlen, die in ein Byte pasten statt in zwei schneller addiert wurden konnten.


Das hat einzig und allein Relevanz für die Informatik, und für sonst nichts.Jein. (http://de.wikipedia.org/wiki/Landau-Symbole)
Mathematiker und Informatiker meinen schon das gleiche und verstehen sich in der Regel auch.
Nur interessiert man sich in der Mathematik meist für andere Aspekte, beispielsweise für das Verhalten einer Funktion aber nicht für die Komplexität, diese Funktion auszurechnen.

mfg

[Monger]

Jein. (http://de.wikipedia.org/wiki/Landau-Symbole)


Grr!
[Klugscheiß]
Informatik ist ein Teilbereich der Mathematik. Natürlich sind alle Symbole und Verfahrensweisen der Informatik auch Bestandteil der Mathematik.
[/Klugscheiß]

[Dr.Doom]

@Dr.Doom
In seinem Beispiel, also bei der Formel [ n*(n+1) ]/ 2, ist das ja aber nicht der Fall, dass bei der Multiplikation die Anzahl der Operationen konstant/vernachlässigbar bleibt. Vorausgesetzt man multipliziert durch wiederholte Addition, sprich wir nehmen jetzt einfach an, dass Multiplikation eine wiederholte Addition ist.Doch. Nicht verwirren lassen, nur weil man zwei n's hat.
Ein Arbeitsschritt des Algorithmus, der das da oben berechnet, heisst ja "irgendwas addieren". Der Arbeitsschritt wird n-mal ausgeführt. Dass jetzt zufällig (n+1) mehrfach addiert wird, ist ja wurscht.

"n * 4 addieren" hat lineare Laufzeit O(n). Für n=10 addiert man 10x die 4.
"n * 4 addieren" hat lineare Laufzeit O(n). Für n=20 addiert man 20x die 4.
"n * n addieren" hat lineare Laufzeit O(n). Für n=10 addiert man 10x die 10.
"n * n addieren" hat lineare Laufzeit O(n). Für n=100 addiert man 100x die 100.
"n * (n+1) addieren" hat lineare Laufzeit O(n). Für n=100 addiert man 100x die (100+1).


Ich bin nicht gut im Erklären, ich sollte es besser lassen. ;) Daher war mein erster Beitrag da oben evtl was unverständlich bzw irreführend, auch wenn ich das richtige gemeint habe. *g*

[wry]

@Dr.Doom
Ok, habe da wohl vorhin deinen Beitrag nicht richtig kapiert :redface:

[pest]

die O-Notation macht nur Sinn wenn man ein entspechendes Rechner-Modell impliziert, das ist m.M. nach meist das Real (Ram) Modell in dem die Grundoperationen mit O(1) ausgeführt werden können. Manchmal ist auch die modulo-operation dabei z.B.

[Expandable]

Ich bin in meiner obigen Ausführung natürlich davon ausgegangen, dass Addition und Multiplikation in konstanter Zeit (O(1)) ausgeführt werden können. Das ist wohl auch der Normalfall. Die O-Notation ist praktisch eh schon sehr fragwürdig. O(n) = O(2n) = O(2000n). Praktisch macht es aber einen riesen Unterschied, ob ich 2000mal so lange warten muss, oder nicht.

[Monger]

Die O-Notation ist praktisch eh schon sehr fragwürdig. O(n) = O(2n) = O(2000n). Praktisch macht es aber einen riesen Unterschied, ob ich 2000mal so lange warten muss, oder nicht.
Wie wir schonmal in einem anderen Thread hier diskutiert haben: Das O Kalkül wird normalerweise dazu verwendet, um die Skalierbarkeit von Algorithmen zu beurteilen.
Alles mit O(n) bzw. darunter wird früher oder später durch ausreichend schnelle Rechner untern Tisch fallen. Alles oberhalb von O(n) (also z.B. O(n²)) wird dir früher oder später das Genick brechen - egal wie schnell dein Rechner ist.

[Expandable]

Wie wir schonmal in einem anderen Thread hier diskutiert haben: Das O Kalkül wird normalerweise dazu verwendet, um die Skalierbarkeit von Algorithmen zu beurteilen.
Alles mit O(n) bzw. darunter wird früher oder später durch ausreichend schnelle Rechner untern Tisch fallen. Alles oberhalb von O(n) (also z.B. O(n²)) wird dir früher oder später das Genick brechen - egal wie schnell dein Rechner ist.

Hmm? Widerspricht das irgendwie dem, was ich gesagt habe?

Mir ist sehr wohl bewusst, wozu man diese Abschätzungen braucht. Das Problem ist halt, dass Algorithmus A mit O(n) theoretisch schneller ist als Algorithmus B mit O(n^2). Dennoch kann A derart hohe Konstanten haben, dass B in allen praktisch relevanten Fällen schneller ist. Darauf wollte ich nur hinweisen.

[pest]

Dennoch kann A derart hohe Konstanten haben, dass B in allen praktisch relevanten Fällen schneller ist. Darauf wollte ich nur hinweisen.

ist aber Unfug, wie sollen diese "großen" Konstanten entstehen?
wenn, ist man wahrscheinlich unfähig einen algorithmus zu entwerfen

[Pinoccio]

ist aber Unfug, wie sollen diese "großen" Konstanten entstehen?
wenn, ist man wahrscheinlich unfähig einen algorithmus zu entwerfenNein, wieso?
Denke doch nurmal an Matrixmultiplikation, wo Strassen's Algortihtmus erst ab ~650 Spalten bzw. Zeilen schneller ist, oder an die Multiplikation großer Zahlen, wo die Grenze (soweit ich wei?) erst bei mehreren tausend Stellen liegt.

mfg

[pest]

eine geeignete problemgröße habe ich stillschweigend vorrausgesetzt, sonst macht die o-notation wenig sinn, weil sie ja eben darüber eine aussage macht.

es wird außerdem kaum vorkommen, das man z.b. 10000 einzelne O(n) schleifen hat

[Monger]

...
Das Problem ist halt, dass Algorithmus A mit O(n) theoretisch schneller ist als Algorithmus B mit O(n^2). Dennoch kann A derart hohe Konstanten haben, dass B in allen praktisch relevanten Fällen schneller ist. Darauf wollte ich nur hinweisen.
Da bewegen wir uns jetzt auf ganz gefährliches Terrain - nämlich das Optimieren (böses Wort!) auf ganz spezielle Anwendungsfälle.

Grundsätzlich sollte man mal davon ausgehen, dass man keine Ahnung hat wie das Benutzerverhalten konkret ist, sprich: mit wievielen Daten mein Algorithmus gefüttert wird.

Wenn mein Programm selbst beim Ausführen einer einzelnen Operation immer noch langsam ist, ist es entweder so dass:

a) mein Programm unnötig viel tut. Dann hat man ein schwerwiegendes Architekturproblem, oder
b) diese Operation schlicht und ergreifend zeitintensiv ist.

Das O-Kalkül ist NICHT dazu da, Aussagen über die reale Performance zu treffen! Die kann man einzig und allein in der realen Anwendung testen. Das O-Kalkül sagt etwas über die Skalierbarkeit aus, nichts anderes.

[samm]

Das O-Kalkül sagt etwas über die Skalierbarkeit aus, nichts anderes.Absolut richtig :) Nicht "geht es 5 Sekunden oder 10", sondern: Wie sehr beschleunigt schnellere Hardware den Algorithmus.

[Expandable]

Das O-Kalkül ist NICHT dazu da, Aussagen über die reale Performance zu treffen! Die kann man einzig und allein in der realen Anwendung testen. Das O-Kalkül sagt etwas über die Skalierbarkeit aus, nichts anderes.

Danke für diese nette Zusammenfassung meiner vorherigen Postings ;) Mehr wollte ich nicht ausdrücken.

[Xmas]

Absolut richtig :) Nicht "geht es 5 Sekunden oder 10", sondern: Wie sehr beschleunigt schnellere Hardware den Algorithmus.
Nein, Hardware die einheitlich x% schneller ist wird jeden Algorithmus x% schneller ausführen. Es geht um die Skalierbarkeit in Bezug auf die Problemgröße.

[Aquaschaf]

ist aber Unfug, wie sollen diese "großen" Konstanten entstehen?
wenn, ist man wahrscheinlich unfähig einen algorithmus zu entwerfen

Die Welt ist doch voll von schönen und asymptotisch optimalen Algorithmen, die gleichzeitig nicht praktikabel sind :)

[samm]

Nein, Hardware die einheitlich x% schneller ist wird jeden Algorithmus x% schneller ausführen. Es geht um die Skalierbarkeit in Bezug auf die Problemgröße.;D Was hat mich da geritten? Hab wohl zu viel mit Hardwarebeschränkungen zu tun. Danke für die Richtigstellung des Offensichtlichen, ist mir ja schon peinlich :redface: