Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
O-Kalkül
Bestimmen Sie die kleinste obere Schranke für folgende Funktion im O-Kalkül
f(n) = summe von i=1 bis n (2*i-1)
Zur Auswahl stehen:
O(n^2)
O(n*logn)
O(n)
Ich würde sagen, dass man die Summenformel in eine for-Schleife umbauen kann (geht das?):
int ergebnis = 0;
for(int i = 1; i <=n; i++) { ergebnis = ergebnis + (2 * i - 1); }
Somit würde ich sagen dass der Aufwand O(n) ist, weil die Schleife n mal läuft.
Was denkt ihr?
genau dieselbe Funktion haben wir mim Stammi besprochen, weil wir genau deinen Einwand hatten, allerdings musst du bei mathematischen Termen Theorie und Praxis unterscheiden.
Die Summe wird mathematisch in der Theorie durch den kleinen Gauss berrechnet, und der sagt (n(n+1))/2. demzufolge ist die Obere Schranke O(n^2)!!!
in deiner Implementierung wirst dus sicher mit einer For-Schleife implementieren, und die hat O(n).
Moral von der Geschichte, wenn du Code Kalkulieren sollst musst du in “Code” denken, wenn du eine Formel vor dir hast, musst du mathematisch umformen…
Jein, deine Begründung ist etwas irreführend.
Man muss zwar unterscheiden zwischen Code und Formel, aber aus einem anderen (einleuchtenden) Grund:
Es geht nicht darum, die gegebene Formel zu implementieren und eine Schranke für die Komplexität der Implementierung zu finden! Die wäre naiv tatsächlich [m]O(n)[/m], mit der Gauss’schen Formel aber sogar nur [m]O(1)[/m], denn [m]f(n) = n^2[/m] (siehe Gaußsche Summenformel – Wikipedia, deine Formel bezieht sich auf eine andere Summe) lässt sich mit einer einzigen Multiplikation und ohne Schleife berechnen.
Es geht aber darum, eine Schranke für die Funktion zu finden, d.h. die gegebene Summe ist quasi schon die Aufwandsfunktion (z.B. für ein beliebiges Stück Code, das nicht gegeben und für die Aufgabe auch nicht relevant ist). Und die liegt eben, wie man an der Summenformel sieht, in [m]O(n^2)[/m] (bzw. ist sogar exakt [m]n^2[/m]).
Danke!
Hilft mir aber irgendwie nicht weiter… Ich dachte, dass mein Gedankengang mal richtig sei und ich was verstanden hätte…
Kann man dann generell sagen, dass die kleinste Obere Schranke bei Summen n^2 ist? Wie ist das, wenn die Summe nicht bei 1 beginnt?
Habt ihr noch mehr so Tricks für mich?
Ich habe mir noch notiert:
f1(n) = 2 falls n <=0
sonst: 2 * f1(n - 1)
hier ist es O(2^n)
könnt ihr das dann auch einfach erklären?
ich hab mir gedacht: man rechnet 222*2…*2 deshalb 2^n
Wie gesagt, ich wäre dankbar, wenn ihr noch so n paar Tricks und Kniffe für mich hättet.
Naja, gefragt ist praktisch das Wachstum der gegebenen Funktion.
Bei der Summe der ungeraden Zahlen wächst es eben “wie” n² (und wie Lup richtig meinte, nicht nur wie, sondern sogar genau n²).
Wenn du z.B. die Funktion f(n) = n³ + 3n² hast, dann wäre das O(n³) (auch wenn du die Funktion in O(1) auswerten könntest).
Bei Rekursionen hat man meist c^n als Wachstum (außer in gewissen Spezialfällen). Wie man das c bestimmt, müsste im Kapitel Rekurrenzen dran sein. Aber dein Gedankengang ist natürlich korrekt.
Nein, einfaches Gegenbeispiel: [m]Summe(i=1…n)( 1 ) = n[/m]
Sondern wo? Kann man nicht so pauschal sagen. Wenn die Summe z.B. bei [m]n[/m] beginnt und bis [m]n[/m] geht… 
Bei der von dir genannten Summe ändert sich für einen konstanten Startwert [m]k[/m], [m]0 < k < n[/m], aber nichts. Da addierst du dann halt nicht [m]n[/m] mal einen [m]O(n)[/m]-Term (-> [m]O(n*n)[/m]), sondern nur noch [m]n-k+1[/m] mal (-> [m]O((n-k+1)*n) = O(n^2)[/m] ).
Ich glaube, in AuD musste man außer für das genannte Beispiel (und sehr ähnliche) keine Umformungen kennen. Der einzige „Trick“ ist auszurechnen, in welcher Größenordnung eine gegebene Funktion liegt, wenn man es anhand ihrer aktuellen Form nicht sofort erkennt, sei es weil sie als Summe definiert ist oder rekursiv oder sonstwie.
[quote]f1(n) = 2 falls n <=0
sonst: 2 * f1(n - 1)
hier ist es O(2^n)
könnt ihr das dann auch einfach erklären?
ich hab mir gedacht: man rechnet 222*2…*2 deshalb 2^n[/quote]
Das hast du doch selbst schon einfach erklärt? 
Die Funktion berechnet für nicht-negative [m]n[/m] rekursiv [m]2^(n+1) = 2^n * 2 = O(2^n)[/m].
Dank euch!
f(n)=log16(5*n³)
[ ]O(n³)
[ ]O(n)
[ ]O(log2n)
bauchgefühl sagt n³ allerdings irritiert mich dann doch das log16 :\
log16(n³)=log₂(n) . Also log₂(n) 
und wie kommt man darauf :scared:
Ich tippe mal auf folgendes:
log16(n³) = 3 * log16(n) (Logarithmengesetze, Potenzen)
= 3 * log₂(n) / log₂(16) i[/i]
= 3 / log₂(16) * log₂(n)
= Konstante * log₂(n)
Genau
Ich habe eine Frage und zwar die Aufgabe 2 aus der letzten Klausur (21.02.2013).
Welchen Laufzeitaufwand hat die Methode foo(n)?
void zoo(int x, int y, int z) {...} // O(1)
void goo(int x) {...} // O(x)
void bar(int x) {...} // O(xlogx)
void foo(int n) {
for (int i = 1; i <= n; i*=2) {
zoo(goo(n), goo(n), bar(n));
}
}for-Schleife ist ja O(logn), aber was mit zoo zu tun, habe ich leider keine Ahnung. Ich vermute, dass man O(max(goo(n),bar(n)) nehmen muss. Also O(xlogx) oder O(nlogn) und dann gesamt O(n(logn)2). Kann mir jemand ein Tipp geben? Danke!
Ich denke es muss O(n * (logn)^2) sein. for schleife hat wie du richtig gesagt hast O(log n). Die zoo läuft in konstanter Zeit, goo in linearer Zeit(maximal O(n)) und bar in O(n log n) Zeit.
So wirklich sicher bin ich mir aber bei dem Kalkül Zeugs auch nie 
Naja, in jedem Schleifendurchlauf werden zweimal goo und einmal bar mit n aufgerufen. Der darauffolgende Aufruf von zoo braucht O(1). ⇒ O(n)+O(n)+O(n log n)+O(1)=O(n log n) pro Schleifendurchlauf. Es sind tatsächlich O(log n) Schleifendurchläufe, insgesamt also O(n log² n).
Anders wäre die Sache, wenn goo und bar mit i statt mit n aufgerufen würden. Dann hätte man insgesamt (über alle Schleifendurchläufe) einen Aufwand von O(log n) für zoo, O(n) für goo und O(n log n) für bar, insgesamt also einen Aufwand von O(n log n) (WolframAlpha hat da geholfen, die Teile aufzusummieren (goo ist noch einfach, weil geometrische Reihe und so, bar nicht mehr ganz so offensichtlich))
alles klar. So ungefähr war auch meine Überlegung. Danke Jungs!