Forum: PC-Programmierung Komplexitätsanalyse einfacher Alogirthmen


von Jochen (Gast)


Lesenswert?

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 ;)

von 6637 (Gast)


Lesenswert?

>Sind folgende Überlegungen ok?
>a) Die For Schleife wird n-1 mal durchlaufen also O(1).


Bist du sicher ? Wie war das nochmals ?

von Jochen (Gast)


Lesenswert?

sorry, tippfehler ;)
Dre rest is richtig?

von 6637 (Gast)


Lesenswert?

b) ist O(N^2) , die 2.Schleife macht nochmals O(N) durchlaeufe.
d) ist eine rekursion (nie gehoert ) damit O(2^N)

von Jochen (Gast)


Lesenswert?

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?

von Karl H. (kbuchegg)


Lesenswert?

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.

von Εrnst B. (ernst)


Lesenswert?

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...

von Jochen (Gast)


Lesenswert?

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".

von Karl H. (kbuchegg)


Lesenswert?

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.

von 6637 (Gast)


Lesenswert?

Log N ist eine binaere Suche, oder ein Quicksort. Man hat einen Aufwand 
fuer jedes zusaetzliche Bit in der Breite. Und das ist Log2(N)

von Netbird (Gast)


Lesenswert?

Ist Quicksort nicht n * log n ?

von Morin (Gast)


Lesenswert?

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.

von Jochen (Gast)


Lesenswert?

Wenn man Aufgabe b abändert in

int k = 0;
for (int i = 0, i<n, i++)
 for (int j = 1; j <4*i, j++)
j = j*2

wäre das dann O(n*logn) ?

von Morin (Gast)


Lesenswert?

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)

von Morin (Gast)


Lesenswert?

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.

von Jochen (Gast)


Lesenswert?

@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?

von Morin (Gast)


Lesenswert?

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.

von Christoph _. (chris)


Lesenswert?

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.

von Arc N. (arc)


Lesenswert?

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.

von Christoph _. (chris)


Lesenswert?

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.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.