Laufzeitanalyse wort case

  • Allgemein

Es gibt 8 Antworten in diesem Thema. Der letzte Beitrag () ist von hal2000.

    Laufzeitanalyse wort case

    Hallo brauche kurz eine Rückmeldung für folgende Aufgabe (Pseudocode):

    C#-Quellcode

    1. 1. n ← length[A]
    2. 2. for i ← n down to 1 do
    3. 3. for j ← 1 to i−1 do
    4. 4. if A[j+ 1]<A[j] then
    5. 5. temp ← A[j]
    6. 6. A[j] ← A[j+ 1]
    7. 7. A[j+1] ← temp


    Da soll man jetzt eine exakte Laufzeitanalyse durchführen, ich habe folgendes raus

    1. 1
    2. n+1
    3. n*((n+1)/2) (Gaußsche Summenformel)
    4. siehe 3
    5. siehe 3
    6. siehe 3
    7. siehe 3

    Dann alles addiert kommt zunächst

    5*(n*((n+1)/2))+(n+1)+1

    =(5n^2+5n)/2+(n+1)+1

    =(5n^2+7n+4)/2

    Das hab Ich dann als Laufzeitfunktion raus, ist das so richtig?

    Was mich auch verwundert ist, dass der Prof (auch an einem anderen Beispiel) in einer Schleife die von 2 bis n ging (bei 1 indiziert), insgesamt n durchläufe für den Schleifenrumpf genommen hat, da beim letzten Aufruf zwar die Schleife nicht ausgeführt, aber trotzdem nach der Bedingung geschaut wird (so hab Ich das verstanden). Im Internet war das aber an allen Beispielen anders, da wurde stets ohne diesen letzten Aufruf gezählt.
    Ich bin zwar kein Profi auf dem Gebiet, aber meine Herangehensweise wäre so:
    Erst mal den Code in möglichst primitive Blöcke zerlegen. Ich verwende dafür jetzt einfach mal C#.

    C#-Quellcode

    1. int[] A; // Ich habe die Deklarationen jetzt einfachheitshalber nach oben geschoben.
    2. int n;
    3. int i;
    4. int j;
    5. int temp;
    6. n = A.Length;
    7. i = n;
    8. while (i >= 1)
    9. {
    10. j = 1;
    11. while (j <= i - 1)
    12. {
    13. if (A[j + 1] < A[j])
    14. {
    15. temp = A[j];
    16. A[j] = A[j + 1]
    17. A[j + i] = temp;
    18. }
    19. j += 1;
    20. }
    21. i -= 1;
    22. }

    Denn jetzt erkennt man besser: Die For-Schleifen bestehen aus jeweils drei Teilen. Initialisierung, Prüfung und Increment/Decrement. Die werden unterschiedlich oft ausgeführt. Deshalb bin ich der Meinung, bei Zeile 2 einfach "n+1" zu zählen ist nicht ganz richtig, weil es mehrdeutig ist.
    Im folgenden Code ist links eingezeichnet, wie oft der Code ausgeführt wird, wobei die Verschachtelung erhalten bleibt:

    C#-Quellcode

    1. 1| int[] A;
    2. 1| int n;
    3. 1| int i;
    4. 1| int j;
    5. 1| int temp;
    6. 1| n = A.Length;
    7. 1| i = n;
    8. 1| n+1| while (i >= 1)
    9. 1| n | {
    10. 1| n | j = 1;
    11. 1| n | i-1+1| while (j <= i - 1)
    12. 1| n | i-1 | {
    13. 1| n | i-1 | if (A[j + 1] < A[j])
    14. 1| n | i-1 | {
    15. 1| n | i-1 | temp = A[j];
    16. 1| n | i-1 | A[j] = A[j + 1]
    17. 1| n | i-1 | A[j + i] = temp;
    18. 1| n | i-1 | }
    19. 1| n | i-1 | j += 1;
    20. 1| n | i-1 | }
    21. 1| n | i -= 1;
    22. 1| n | }

    Wie oft eine Zeile tatsächlich ausgeführt wird, ergibt sich, indem man alle Faktoren links zusammenmultipliziert.
    Beachte auch, dass die Prüfung der Schleifen immer einmal öfter ausgeführt wird, als der Inhalt, da nicht nur nach jedem der n Durchläufe geprüft wird, sondern auch einmal vor dem ersten Durchlauf.
    1 und n sind konstant, also die Zeilen, die nur aus 1 und n bestehen, sind einfach. Aber i-1 hängt vom aktuellen Wert von i ab, welcher nicht konstant ist. Da muss man jetzt etwas nachdenken.
    Im ersten Durchlauf der äußeren Schleife hat i den Wert n. Der Inhalt der inneren Schleife läuft dann von 1 bis n-1 durch. Das ist n-1 mal. Die Prüfung einmal mehr, also n mal.
    Im letzten Durchlauf der äußeren Schleife hat i den Wert 1. Der Inhalt der inneren Schleife läuft dann von 1 bis 0 durch. Da 0 hier direkt am Anfang zu klein ist, läuft der Inhalt garnie (aber die Prüfung trotzdem einmal).
    Also die inneren Zeilen (bei "i-1") laufen erst 0 mal, dann 1 mal, dann 2 mal, dann ... und dann n - 1 mal durch.
    Und die Prüfung der inneren Schleife (bei "i-1+1") laufen erst 1 mal, dann 2 mal, dann 3 mal, dann ... und dann n mal durch.
    Das sind sogenannte "Triangle Number".
    Für ersteres ergibt sich 1/2 * (n - 1) * n bzw. (n² - n) / 2: wolframalpha.com/input/?i=sum+of+i+for+i+%3D+0+to+(n+-+1)
    Und für letzteres 1/2 * (n + 1) * n bzw. (n² + n) / 2: wolframalpha.com/input/?i=sum+of+i+for+i+%3D+0+to+n
    Das Gesamtergebnis ist also folgendes:

    C#-Quellcode

    1. 1 | int[] A;
    2. 1 | int n;
    3. 1 | int i;
    4. 1 | int j;
    5. 1 | int temp;
    6. 1 | n = A.Length;
    7. 1 | i = n;
    8. n+1 | while (i >= 1)
    9. n | {
    10. n | j = 1;
    11. (n² + n) / 2 | while (j <= i - 1)
    12. (n² - n) / 2 | {
    13. (n² - n) / 2 | if (A[j + 1] < A[j])
    14. (n² - n) / 2 | {
    15. (n² - n) / 2 | temp = A[j];
    16. (n² - n) / 2 | A[j] = A[j + 1]
    17. (n² - n) / 2 | A[j + i] = temp;
    18. (n² - n) / 2 | }
    19. (n² - n) / 2 | j += 1;
    20. (n² - n) / 2 | }
    21. n | i -= 1;
    22. n | }

    Beziehungsweise kann man es etwas vereinfachen, um auf den ursprünglichen Code zurückzukommen:

    C#-Quellcode

    1. 1 |n ← length[A]
    2. 1 |for i: i = n
    3. n+1 |for i: i >= 1
    4. n | for j: j = 1
    5. (n² + n) / 2 | for j: j <= i - 1
    6. (n² + n) / 2 | if A[j + 1] < A[j] then
    7. (n² + n) / 2 | temp ← A[j]
    8. (n² + n) / 2 | A[j] ← A[j + 1]
    9. (n² + n) / 2 | A[j + 1] ← temp
    10. (n² + n) / 2 | for j: j += 1
    11. n |for i: i -= 1

    Aber das jetzt einfach alles zusammenzuaddieren, kann nicht gutgehen. A[j] ← A[j + 1] macht mehr als temp ← A[j], also kann es nicht gleichgestellt sein. Man könnte den Code jetzt weiter runterbrechen auf Additionen, Subtraktionen, Array-Indexierungen (schreibend und lesend), Zuweisungen und Bedingte Sprünge. Dann könnte man die gruppieren und zusammenzählen. Aber da stellt sich halt die Frage, wie man diese "minimalistischen Schritte" wählt. Denn kompiliert man den Code z.B. zu x86, kommt es drauf an, ob die diversen Variablen auf dem Stack liegen, oder doch in Registern. Oder wenn man nur den MSIL-Code betrachtet, zählt man dann die Anzahl an Stack-Operationen? Es kommt immer darauf an, was man erreichen will. Aber ein Rezept für alle gibt es meines Wissens nach nicht.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils
    Definiere

    RushDen schrieb:

    exakte Laufzeitanalyse
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    @Niko Ortner

    Deine Erklärungen und alles sind zwar richtig, aber bei einer exakten Laufzeitanalyse werden solche Dinge nicht berücksichtigt z.B. dass ein Befehl mehr Zeit als ein anderer Befehl braucht oder wie du die Schleifen auseinander genommen hast, das wird alles nicht gemacht (hat der Prof in seinem Beispiel auch nicht und extra erwähnt dass man am Ende in der O Notation die Konstanten wegstreicht da diese irrelevant sind), damit sind die oben genannten Faktoren irrelevant.

    Die O Notation ist ja auch gerade dafür gedacht unabhängig von der Hardware und Software eine Laufzeitgeschwindigkeit anzugeben, also lediglich abhängig von der Eingabegröße.

    @RodFromGermany

    Auf der Aufgabe stand halt exakte Laufzeit im Worst Case Fall.

    Im Skript hat er Insertion Sort auf diese Art gemacht, also Pseudocode aufgestellt und dann Zeile für Zeile durchgegangen und am ende alles zusammenaddiert.

    Die frage ist nur ob das richtig ist wie oft die jeweiligen Zeilen aufgerufen werden ?

    RushDen schrieb:

    Worst Case
    Sieh Dir mal Deinen Thread-Titel an. :D :D
    Ich denke mal, die Aufgabe ist so nicht exakt zu lösen, wie es dem Aufgabensteller vorschwob.
    Im Worst Case läuft auf dem PC noch eine Konvertierung eines Films von TS nach MP4 mit FFMPG, da kannst Du keine Zeiten zusammenzählen, sondern kannst nur am Beginn eine Stopwatch starten und sie am Ende auslesen, das ganze machst Du unter echten Stress-Bedingungen mindestens 10 Mal und dann hast Du eine Liste von Zeiten, über die Du Dich wahrscheinlich wundern wirst.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Also geht es Dir bzw. Deinem Prof um das hier?
    Dazu formst Du alles so um, dass eine Funktion in der Richtung a + b + c + d + ... rauskommt. Also musst du nur bei (n² - n) / 2 die Klammer auflösen: n² / 2 - n / 2 bzw. 1/2 * n² - 1/2 * n. Und dann den Summanden raussuchen, der am schnellsten wächst, wenn n wächst. Das ist hier 1/2 * n². Konstante Faktoren kann man weglassen, dann bleibt übrig. Also ergibt sich für diesen Code O(n²).
    Wie gesagt, ich bin kein Profi auf dem Gebiet, aber wenn ich das richtig verstehe, kann man bei diesem Code alles zusammenaddieren und dann den am schnellsten wachsenden Summanden raussuchen, und es kommt das selbe Ergebnis raus. Aber ob das generell sinnvoll ist, kann ich nicht beurteilen.
    Exakt ist O(n²) jedenfalls nicht. Exakt wäre das, was ich oben gemacht habe, wo für jede Zeile angegeben ist, wie oft sie ausgeführt wird.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils
    Hi
    wenn man's genau nimmt: O(n²) ist exakt, es handelt sich um eine Menge, die alle Funktionen enthält, die "nicht wesentlich schneller wachsen", als n². Daher ist auch die Notation f = O(g) syntaktisch eigentlich nicht richtig. Zumindest in der Informatik macht man's halt trotzdem.
    Es gibt in der Analyse von Algorithmen übrigens weitaus exaktere Verfahren zur Analyse.

    Viele Grüße
    ~blaze~

    Niko Ortner schrieb:

    Also geht es Dir bzw. Deinem Prof um das hier?
    Dazu formst Du alles so um, dass eine Funktion in der Richtung a + b + c + d + ... rauskommt. Also musst du nur bei (n² - n) / 2 die Klammer auflösen: n² / 2 - n / 2 bzw. 1/2 * n² - 1/2 * n. Und dann den Summanden raussuchen, der am schnellsten wächst, wenn n wächst. Das ist hier 1/2 * n². Konstante Faktoren kann man weglassen, dann bleibt übrig. Also ergibt sich für diesen Code O(n²).
    Wie gesagt, ich bin kein Profi auf dem Gebiet, aber wenn ich das richtig verstehe, kann man bei diesem Code alles zusammenaddieren und dann den am schnellsten wachsenden Summanden raussuchen, und es kommt das selbe Ergebnis raus. Aber ob das generell sinnvoll ist, kann ich nicht beurteilen.
    Exakt ist O(n²) jedenfalls nicht. Exakt wäre das, was ich oben gemacht habe, wo für jede Zeile angegeben ist, wie oft sie ausgeführt wird.


    Das ist die asymptotische Laufzeitbestimmung (die bekomm Ich auch hin und kommt dannach), mir gehts ja erstmal um die Bestimmung der Funktion an sich (quasi indem Ich zähle wie oft der Pseudocode im schlechtesten Fall (wenn die Eingabe absteigend sortiert ist) durchlaufen wird (in abhängigkeit zur Länge der Eingabe).
    Ich hab übrigens einen Fehler entdeckt: die zweite For-schleife wird jeweils 1x öfter aufgerufen (Rumpfbedingung prüfen) und deshalb muss da ((n+1)*n)/2 und bei den nachfolgenden Zeilen (n*(n-1))/2 sodass Ich am Ende auf die Funktion 1/2*(5n^2-n+4) komme (zusammengefasst).

    und wie blaze schon erwähnt hat ist die groß O Notation die Menge aller Funktionen für die c * f(n) in O(f(n)) eine obere Schranke ist wobei ein beliebiges c > 0 existieren muss und nicht eine konkrete Laufzeitangabe (sondern mehr eine Verallgemeinerung von Laufzeitangaben)

    @RodFromGermany

    Nein, das ist ein standatisiertes Verfahren in der jegliche Faktoren wie Hardware/Software völlig ausser acht gelassen werden und nur die Anzahl der Codezeilen die ausgeführt werden muss, um mit n Elementen einen Algorithmus zu terminieren, bestimmt wird. Die ändert sich nicht selbst wenn 100 Videos nebenbei konvertiert werden, weil es nicht auf die Zeit im Sinne von Minuten/Sekunden ankommt, sondern auf die Anzahl der Codezeilen die ausgeführt werden müssen. Die Frage ist ja nur ob Ich das oben richtig gezählt habe wie oft die Funktion im schlechtesten Fall aufgerufen wird
    Wichtig sind für die Bestimmung der Laufzeitkomplexität später nur zwei Dinge:
    - Du findest den korrekten Term für die O-Notation (in diesem Fall n^2). Die Koeffizienten des Polynoms, das du im ersten Schritt bestimmst, sind relativ egal, solange nur der Grad stimmt. Je nach Interpretation und Laune des Bearbeiters existieren mehrere richtige Lösungen für das Polynom, aber nur eine (sinnvolle) für den Term.
    - Du kannst den Beweis für den gefundenen Term führen. Nimm dazu einfach den Term aus dem O, wähle ein c und berechne den dafür erforderlichen Startwert n_0, ab dem die Aussage der O-Notation stimmt.

    Die Aussage ist übrigens f(n) in O(g(n)) <=> es gibt c > 0 sd. f(n) <= c * g(n) für alle n > n_0.
    Gruß
    hal2000