Hallo, sind gerade dabei, für eine Klausur zu lernen, haben aber noch
ein paar Schwierigkeiten.
Die Aufgabe lautet:
Bestimmen Sie die Zeitkomplexität in Abhängigkeit der Eingabe n (einer
positiven ganzen Zahl) der folgenden Algorithmen, wobei die
Grundrechenarten, Speicherzugriffe und Vergleiche die Komplexität O(1)
haben.
Man kann jeweils ankreuzen:
O(1), O (log n), O(n), o(n log n), O(n^2), O(n^3), O(2^n)
a)
int max = a[0];
for (int i = 1; i <n, i++)
if (a[i] > max)
max = a[i];
b)
int k = 0;
for (int i = 0, i<n, i++)
for (int j = 1; j <4*i, j++)
k += j;
c)
int t = 1
while (t <=n)
t = 2*t;
d)
Aufruf der folgnden Methode mit calc (n)
static int calc (int i) {
if (i ==0)
return 1
return calc (i-1) + calc(i-1);
e)
Aufruf der folgnden Methode mit isEven(n)
static boolean isEven(int i) {
switch (i) {
case 0: return true;
case 1: return false;
default: return isEven(i-2);
}
}
Sind folgende Überlegungen ok?
a)
Die For Schleife wird n-1 mal durchlaufen also O(1).
b) Die erste for Schleife hat die Komplexität O(n). Was bedeutet bei der
zweiten k+=j? Bekommt nur k einen neuen Wert, dann hat diese Zeile ja
keinen Einfluss und die zweite Schleife hat auch O(n) also insgesamt
O(n^2).
c) log(n). Denn mit zunehmendem n erreicht man dieses zwar immer länger,
aber da verdoppelt wird auch relativ schnell ?! Oder wie kommt man auf
das Ergebnis, es ist zwar klar irgendwoher, aber wie kann man es exakt
bestimmen?
d)
Andere Frage: wie oft wird die Methode calc (i-1) aufgerufen?
Und zwar O(n + n) = O(2n) * O(n)
e)
Andere Frage: wie oft wird die Methode aufgerufen?
zwar immer i-2, aber je größer die Zahl, desto mehr aufrufe
also O(n).
Also fast immer nur O(n) angekreuzt ?!?
Dankeschön ;)
Vielen dank für deine Hilfe.
b) hab ich ja auch so.
Wieso schreibst du u den anderen nichts? Ist dir b und d nur spontan
eingefallen, oder stimmt der Rest?
Wieso:
"d) ist eine rekursion (nie gehoert ) damit O(2^N)"
Das verstehe ich nicht.
Es wird ja immer eins abgezogen und die Rekursion nochmals aufgeruen. is
man bei der 0 ist. Also z.B.
n = 5
5 , 4, 3, 2, 1,
das ganze passiert zweimal
Wie kommt man da auf 2^n?
Jochen wrote:
> n = 5> 5 , 4, 3, 2, 1,> das ganze passiert zweimal
Aber für jeden der beiden Teilzweige teilt es sich dann wieder in
2 Teile.
> Wie kommt man da auf 2^n?
calc(5)
/ \
calc(4) calc(4)
/ \ / \
calc(3) calc(3) calc(3) calc(3)
/ \ / \ / \ / \
calc(2) calc(2) calc(2) calc(2) calc(2) calc(2) calc(2) calc(2)
/ \ / \ ......
c(1) c(1) c(1) c(1)
Bei derartigen Binärbaum Strukturen ist der Trick praktisch immer
darin zu suchen, dass du 2^n-1 Knoten in einem Baum mit der Höhe n
anordnen kannst. Hier, bei der Komplexitätsanalyse ist es genau
umgekehrt: Du hast die Baumhöhe gegeben und willst wissen wieviele
Knoten da drinn Platz haben (weil jeder Knoten eine Berechnung
darstellt). Bei einer Baumhöhe von n brauchst du daher 2^n-1
Berechnungen. Die -1, als konstanter Anteil, fallen unter den
Tisch.
Wenns für ne Übungsaufgabe und nicht für eine Klausur ist, kannst du das
Moore'sche Gesetz mit einberechnen:
Alle 1,5 Jahre verdoppelt sich die Leistungsfähigkeit der Computer.
die Konstante "1.5 Jahre" fliegt in der O-Notation natürlich raus, also
wird jeder Rechenschritt in der halben Zeit des vorhergehenden
ausgeführt...
Danke für die Zeichnung und den Beitrag :D
Wenn bei dieser Aufgabe
return calc (i-1) + calc(i-1) + calc(i-1);
dort stehen würde, hätte man 3^n, oder?
Sind die anderen Aufgaben korrekt?
Wie kann man log n erkennen, ich mach das immer nach "Gefühl".
Jochen wrote:
> Wie kann man log n erkennen, ich mach das immer nach "Gefühl".
log n liegt zb dann vor, wenn du in besagtem Baum was suchst.
Wenn also die Suchmenge in 2 Hälften geteilt wird und abhängig
vom Suchparameter entweder die eine Hälfte oder die andere
Hälfte weiter untersucht wird.
n ist die Menge der verfügbaren Knoten.
Bis auf den Tippfehler bei a) stimmt's.
> Ist Quicksort nicht n * log n ?
Ist es. Da muss 6637 was verwechselt haben. Binäre Suche ist aber
wirklich O(log n) sofern der Suchbaum nicht degeneriert ist.
Das "int k=0" verwirrt mich etwas weil es weiter nicht benutzt wird.
Wolltest du vielleicht was anderes schreiben?
So wie es jetzt da steht ist es immer noch O(n^2): Die äußere Schleife
wird n-mal durchlaufen. Die innere wird 4*(i-1)-mal durchaufen, das sind
im Mittel über alle Durchläufe der äußeren Schleife O(n) (*), also
insgesamt O(n^2) Durchläufe der inneren Schleife.
(*) Mittel {0, 4, 8, 12, ..., 4*(n-2), 4*(n-1)}
= 4 * Mittel {0, 1, 2, ..., n-2, n-1}
= 4 * Summe {0, 1, 2, ..., n-2, n-1} / n
= 4 * (n-1) * (n-2) / (2n)
= 2 * (n-1) * (n-2) / n
= O(n)
STOP ich ziehe alles zurück, habe die Multiplikation von j in der
inneren Schleife übersehen. Leider weiß ich nicht wie man hier im Forum
was editieren oder löschen kann.
@Morin:
Dass das k nicht mehr benutzt wird, liegt daran, dass ich genau diese
Zeile, wo es benutzt wird, verändert habe ;)
Danke, für dein Mühe.
Stimmt es denn, dass der Aufwand davon O(n logn ) ist?
Hab leider erst jetzt weder Zeit. Also: Die Analyse wird etwas
komplizierter, weil in der inneren Schleife das j sowohl verdoppelt als
auch pro Durchlauf 1 addiert wird. Das heißt aber dass nach P
Durchläufen
j = ...2*(2*(2*1+1)+1)+1...
= 2^P + 2^(P-1) + 2^(P-2) + ... + 1
= 2^(P+1)-1
<! 4*i
und damit alle Durchläufe der inneren Schleife zusammen genommen in
O(log i) durchlaufen werden. Also liegt die insgesamt benötigte Zeit in
der Ordnung
log 1 + log 2 + log 3 + ... + log n
= log (n!)
Ich bin jetzt allerdings nicht sicher ob O(log (n!)) und O(n*log n)
dasselbe sind oder ob ersteres "kleiner" ist.
Nur der Vollstaendigkeit halber: Quicksort ist in O(n^2), aber nicht in
O(n log n). Wenn du einen O(n log n)-Sortier-Algorithmus brauchst, musst
du etwas anderes nehmen wie zum Beispiel Heapsort.
Der Grund ist, dass die Gross-O-Notation eine obere Schranke angibt und
keine mittlere Laufzeit. Quicksort wird bei bestimmten (z.B.
vorsortierten) Eingabedaten quadratische Laufzeit benoetigen, daher ist
Quicksort nicht mehr in O(n log n).
Uebrigens: Praktisch jeder uebliche Algorithmus ist in O(n!). Denn O(f)
fuer irgendeine Funktion f ist in Wirklichkeit eine Menge mit der
Eigenschaft dass sie alle Funktionen enthaelt, die hoechstens so schnell
wachsen wie f. Ein Algorithmus der in O(n log n) ist, ist also
automatisch auch in O(n^2), O(n^3), O(2^n) und vielem mehr.
Wenn die Aufgabe also zum Ankreuzen ist und man korrekt sein will, muss
man neben der niedrigsten auch alle hoeheren Schranken ankreuzen.
Ansonsten ist das mathematisch gesehen einfach falsch.
Christoph __ wrote:
> Nur der Vollstaendigkeit halber: Quicksort ist in O(n^2), aber nicht in> O(n log n). Wenn du einen O(n log n)-Sortier-Algorithmus brauchst, musst> du etwas anderes nehmen wie zum Beispiel Heapsort.> Der Grund ist, dass die Gross-O-Notation eine obere Schranke angibt und> keine mittlere Laufzeit. Quicksort wird bei bestimmten (z.B.> vorsortierten) Eingabedaten quadratische Laufzeit benoetigen, daher ist> Quicksort nicht mehr in O(n log n).
Quicksort ist in O(n log n), da n nicht die Art der Eingabedaten
bestimmt, sondern nur deren Anzahl (rekursive Laufzeitgleichungen).
Will man das ganze auch im Worst-Case in n log n, nimmt man den Median
zum partitionieren.
Ok, ich war unpraezise. Dass n die Anzahl der Eingabedaten angibt, ist
mir selbstverstaendlich bekannt, wie sollte eine natuerliche Zahl auch
die Art der Eingabedaten angeben?
Zu Quicksort:
Wenn man den Median als Pivot nimmt funktioniert es tatsaechlich in
O(n log n), vorausgesetzt man bekommt den Median in linearer Zeit, was
nicht ganz trivial ist. Bei meiner Betrachtung oben bin ich von naivem
Quicksort ausgegangen, dass zum Beispiel immer das erste Element des
Arrays als Pivot benutzt. Dann ist Quicksort in O(n^2), weil es eben
Eingabedaten der Laenge n gibt bei denen die Schranke O(n log n)
ueberschritten wird.
