www.mikrocontroller.net

Forum: PC-Programmierung Komplexitätsanalyse einfacher Alogirthmen


Autor: Jochen (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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 ;)

Autor: 6637 (Gast)
Datum:

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


Bist du sicher ? Wie war das nochmals ?

Autor: Jochen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
sorry, tippfehler ;)
Dre rest is richtig?

Autor: 6637 (Gast)
Datum:

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

Autor: Jochen (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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?

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht 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...

Autor: Jochen (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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".

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: 6637 (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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)

Autor: Netbird (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ist Quicksort nicht n * log n ?

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Jochen (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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) ?

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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)

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Jochen (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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?

Autor: Morin (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Christoph __ (chris)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Arc Net (arc)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Christoph __ (chris)
Datum:

Bewertung
0 lesenswert
nicht 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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.