Informatikraben - Kompexitaet von Algorithmen

Liebe interessierte Neu-Rabeneltern,

wenn Ihr Euch für das Forum registrieren möchtet, schickt uns bitte eine Mail an kontakt@rabeneltern.org mit eurem Wunschnickname.
Auch bei Fragen erreicht ihr uns unter der obigen Mail-Adresse.

Herzliche Grüße
das Team von Rabeneltern.org
  • Hallo,


    gibt es hier jemanden, der mir DAU verstaendlich erklaeren kann wie die Kompexitaet von einfachen Algorithmen berechnet wird und wie dann BigOmega, Theta... bestimmt wird? Ich bin so bloed ich kapier's einfach nicht...


    Beispiel:

    Matrix A (mxn) and b (nx1)


    for i = 1 to m do

    x(i) = 0

    for j = 1 to n do

    x(i) = x(i) + A(i,j) *b


    wenn ich mir aus der Loesung zu einem aehnlichen Problem etwas zusammen klaube:

    for i = 1 to m do cost: 2 m mal -> 2m

    x(i) = 0 cost 1 n mal -> n

    for j = 1 to n do cost: 2 n mal -> 2n

    x(i) = x(i) + A(i,j) *b cost 3(?) wie oft? -> lost...


    Hilfe...

  • Ich kann mir das heute Abend Mal versuchen anzugucken. Leider kann ich das in dem unformatierten Format nicht gut lesen.

    Kannst du das nochmals formatiert abtippen oder per Hand und dann ein Bild davon?

    • Offizieller Beitrag
  • Hinter dem b fehlt noch das j, also so:


    (1) for i = 1 to m do

    (2) x(i) = 0

    (3) for j = 1 to n do

    (4) x(i) = x(i) + A(i,j) *b(j)


    Schritt (1) gibt an, dass die Schritte (2) -(4) m-mal ausgeführt werden, also hat man schon mal theta(m*(...)).


    Schritt (2) ist eine einfache Zuweisung mit konstantem Zeitaufwand (vorausgesetzt der Zugriff auf die Elemente des Vektors ist in konstanter Zeit möglich, wovon man aber ausgehen kann). Konstanten sind in der Komplexitätstheorie uninteressant und werden einfach weggelassen. In der Praxis können Konstanten natürlich trotzdem eine große Rolle spielen, aber in der Theorie geht es nur um die Frage, ob die Funktion linear, quadratisch, exponentiell, etc. ist. Die Komplexität ist also immer noch theta(m*(...)).


    Schritt (3) sagt, dass Schritt (4) n-mal ausgeführt wird, das ergibt als theta(m*n*(...)).


    Der Aufwand von Schritt (4) ist konstant, da alle einzelnen Operationen konstanten Zeitaufwand haben (Werte auslesen, addieren, multiplizieren, Werte zuweisen) und es eine feste Anzahl an Operationen gibt. Daher ändert sich nichts an der Komplexität und es bleibt bei theta(m*n).


    Omega gibt eine untere Schranke an (also eine Funktion, die langsamer oder genauso schnell wächst), da könnte man sowohl Omega(m*n) als auch z. B. Omega(m), Omega(n) oder Omega(1) nehmen.


    Dann gibt es noch O, das gibt eine ober Schranke an, da könnte man O(m*n) oder auch O(m^2*n^2) oder O(e^(m*n)) usw. nehmen.


    Und theta ist dann die Funktion, die genau passt, also die man sowohl für Omega als auch for O nehmen kann (in diesem Fall dann theta(m*n)).


    Hier ist die Verwendung der Symbole nochmal ausführlicher erklärt: Landau-Symbole

  • Liese


    Danke für den Link. Denn werd ich mir merken. Ich hadere auch immer wieder mit solchen Angaben (wusste nicht mal wie sie heißen #schäm). Jetzt kann ich bei Bedarf nachlesen #top.

    Yeza


    My life falling apart

    Over and Done!