Landau-Symbole

Ziegen Sie dass

$\sum_{i=1}^{n} i$

den Aufwand O(n^2) hat.

Das geht mir irgednwie gar nicht ein, ich hätte eher auf O(n) getippt.

Wie geht man bei wo etwas am besten vor?

SeppJ

O(n^2) schließt O(n) ein.

Achja, so war das, aber ich frage mich immer noch:

Wie gehe ich bei so einer Aufgabe vor, ich kann ja nicht anfangen die Operationen zu zählen.
Kann mir einer anhand dieses einfachen Beispiels zeigen wie das geht?
(Bin zu blöd bei google was brauchbares zu finden)

ALso ich möchte jetzt zeigen, dass das O(n) ist. Wie beweise ich das?

Wer stellt denn so eine saublöde Aufgabe?

Es ist trivial, dass eine einfache Summe von 1 bis n linearen Berechnungsaufwand hat.

Kann es sein, dass Du etwas anderes zeigen sollst? Nämlich dass die Summe bereits den Aufwand eines Algorithmus angibt und du somit zeigen sollst, dass er quadratisch ist? (Gaußsche Summe)

Bashar

summerfag schrieb:

Wer stellt denn so eine saublöde Aufgabe?

Es ist trivial, dass eine einfache Summe von 1 bis n linearen Berechnungsaufwand hat.

Es ist noch viel schlimmer. Eine einfache Summe hat überhaupt keinen Berechnungsaufwand, ein bestimmter Algorithmus (mit Maschinenmodell) zum Berechnen der Summe hat einen.

Kann es sein, dass Du etwas anderes zeigen sollst? Nämlich dass die Summe bereits den Aufwand eines Algorithmus angibt und du somit zeigen sollst, dass er quadratisch ist? (Gaußsche Summe)

Glaub ich auch.

SG1

shisha schrieb:

ALso ich möchte jetzt zeigen, dass das O(n) ist. Wie beweise ich das?

Gar nicht, weil's nicht in O(n) ist.

Um Missverständnissen vorzubeugen, poste ich mal die Aufgabenstellung:

Zeigen Sie, dass f(n) = O(n^2) für f(n) = SUMME von i = 1 bis n (i)

Latex scheint nicht zu wollen (und ja ich habe in mathematischen Modus gewechselt), deswegen diese grausige Darstellung.
Das ist die gesamte Aufgabe, keine weiteren Angaben, kein Algorithmus, nichts. Nur eine Funktion f(n).

Die zweite AUfgabe wäre:
Bestimmen Sie die Laufzeit der Methode foo in O-Notation. Welche Funktion
berechnet die Methode (geben Sie eine Formel mit hochstens einem Summen-
zeichen an)?

static int foo(int n) {
 int c = 0;
 for (int i = 0; i < n; i++)
 for (int j = i; j < n; j++)
 c = c + j;
 return c;
}

shisha schrieb:

Um Missverständnissen vorzubeugen, poste ich mal die Aufgabenstellung:

Zeigen Sie, dass f(n) = O(n^2) für f(n) = SUMME von i = 1 bis n (i)

f(n) = n*(n+1)/2 und das liegt in O(n^2). Das und nichts anderes sollst du zeigen.

Michael E.

SG1 schrieb:

shisha schrieb:

ALso ich möchte jetzt zeigen, dass das O(n) ist. Wie beweise ich das?

Gar nicht, weil's nicht in O(n) ist.

Sei S die Summe der Zahlen von 1 bis n.
Behauptung: S € O(n).
Induktionsanfang: n = 1: S(1) = 1.
Induktionsschritt: n -> n+1: S(n+1) = S(n) + n+1. S(n) € O(n) und n+1 € O(n). Also ist auch die Summe O(n) + O(n) = O(n).

Es gibt diesen "Beweis" auch in viel schönerer Form, bei der man wirklich einen Moment überlegen muss, um den Fehler zu finden. Diese Version fällt mir aber leider nicht mehr ein.

Jester

Michael E. schrieb:

SG1 schrieb:

shisha schrieb:

ALso ich möchte jetzt zeigen, dass das O(n) ist. Wie beweise ich das?

Gar nicht, weil's nicht in O(n) ist.

Sei S die Summe der Zahlen von 1 bis n.
Behauptung: S € O(n).
Induktionsanfang: n = 1: S(1) = 1.
Induktionsschritt: n -> n+1: S(n+1) = S(n) + n+1. S(n) € O(n) und n+1 € O(n). Also ist auch die Summe O(n) + O(n) = O(n).

Und, findest du auch den Fehler selbst? Schreib mal Deine Induktionsvoraussetzung hin.

edit: du mußt das O(n) expandieren, du schiebst gerade den ganzen aufwand in die konstante -- die dann halt nicht mehr konstant ist.

ach, ich machs einfach selbst: S(n) in O(n) ist nix anderes als S(n) <= c*n für n>=n_0 für ein *festes* c. Probier jetzt mal Deinen "Beweis" sauber durchzuziehen.

edit2: aha, du hast auch editiert...

Michael E.

Jester: Man muss nicht mal so ins Detail gehen, wenn man verstanden hat, dass O(n) eine Klasse von Funktionen ist und S(n) = O(n) eigentlich S(n) € O(n) bedeutet. Denn im Induktionsschritt benutze ich den Funktionswert S(n) und sage, dass dieser in O(n) liegt. Das macht aber keinen Sinn. Das kommt davon, wenn man schlampige Schreibweisen benutzt

Nachdem ich nun gar nichts mehr kapiere

f(n) = n*(n+1)/2 und das liegt in O(n^2). Das und nichts anderes sollst du zeigen.

Ist das wirklich was ich zeigen soll?

Und ist der Algorithmus

s = 0
for i =1, i<=n , i++:
  s += i

jetzt O(n) oder O(n^2)??

Michael E.

shisha schrieb:

Nachdem ich nun gar nichts mehr kapiere

f(n) = n*(n+1)/2 und das liegt in O(n^2). Das und nichts anderes sollst du zeigen.

Ist das wirklich was ich zeigen soll?

Das kann man so machen, muss man aber nicht. Du musst eigentlich nur eine quadratische obere Schranke für f finden. n*(n+1)/2 ist zwar eine quadratische obere Schranke, aber es gibt eine noch einfachere, bei der du fast nichts mehr zeigen musst.

Edit: Tipp: Überlege dir, warum 1+2+...+n kleiner gleich n*n ist.

Und ist der Algorithmus
s = 0
for i =1, i<=n , i++:
  s += i
jetzt O(n) oder O(n^2)??

O(n^2).

Jester

Michael E. schrieb:

Und ist der Algorithmus
s = 0
for i =1, i<=n , i++:
  s += i
jetzt O(n) oder O(n^2)??
O(n^2).

nein, der ist linear. -- zumindest wenn man auf Spitzfindigkeiten verzichtet...

Der Punkt ist, Du hast eine Funktion gegeben und sollst zeigen, dass sie in O(n^2) liegt. Dass man den Funktionswert mit einem Algorithmus berechnen kann (der eine andere Laufzeit hat) und dass es überhaupt Algorithmen gibt hat damit schlicht garnichts zu tun. Es geht nur um Funktionen.

Michael E.

Jester schrieb:

Michael E. schrieb:
Und ist der Algorithmus
s = 0
for i =1, i<=n , i++:
  s += i
jetzt O(n) oder O(n^2)??
O(n^2).
nein, der ist linear. -- zumindest wenn man auf Spitzfindigkeiten verzichtet...

Ach verdammt, hab mich auf die Ausgabegröße bezogen und nicht auf die Laufzeit. Da hast du natürlich recht.