Algorithmen Analyse einer Schleife

[JavaUndC-Prog]

Guten Tag,

ich bin im Netz auf interessante Folien zum Thema Analyse von Algorithmen gestoßen. Dort wird beispielsweise ein einfacher Programmcode analysiert. Das ist diese typische Frage nach, wie oft wird Operation XY ausgeführt bzw. was sind die Kosten des Algos. Jetzt habe ich selber einmal meine Analyse gestartet und stimme nicht mit dem überein, was dort gesagt wird. In großen Teilen und unter gewissen Annahmen kann ich manchem jedoch zustimmen. Ich halte das mal relativ einfach um was es hier im Kern geht.

Angenommen es gibt eine typische Schleife, wie diese hier:

for(int i = 1; i < n; i++){
    // Anweisung
}

Jetzt ist die Frage nach der Anzahl der Ausführungen. Das demonstriere ich mal anhand einiger Szenarien:
Fall n = 0:
int i = 1 // wird 1x ausgeführt
i < n // wird 1x ausgeführt, danach Exit...

Fall n = 1:
int i = 1 // wird 1x ausgeführt
1 < n // wird 1x ausgeführt, danach Exit

Fall n = 2:
int i = 1 // wird 1x ausgeführt
i < n // wird 1x ausgeführt
Anweisung kommt
i++ // wird 1x ausgeführt
1 < n // wird 1x ausgeführt, danach Exit

Jetzt wird für die Schleife folgendes behauptet:

• int i = 1 wird einmal ausgeführt // kann ich bestätigen
• i < n // wird n mal ausgeführt // kann ich nicht bestätigen (siehe Fall n = 0), würde man die n = 0 als Fall streichen, stimmt das!
• i++ wird n-1 mal ausgeführt // fast, würde stimmen, wenn der Fall n = 0 nicht beachtet werden würde

Das bringt mich zu folgendem allgemeinen Schluss, würde man die 0 als Fall auslassen, könnte man allgemein für die Schleife behaupten, dass in Summe: 1 (für int i = 1) + n + (n-1) Operationen ausgeführt werden. Bei der Analyse von Algorithmen würde man in diesem Beispiel den Fall 0 einfach wegfallen lassen, oder würde der als Sonderfall gehandhabt werden? Was meint ihr?

 

[mihe7]

Fall 0 und 1 sind identisch: die Schleife terminiert ohne Iteration. Bis dahin sind zwei Schritte nötig, nämlich die Initialisierung und der Vergleich. Jeder Iteration folgen zwei Operationen, nämlich ein Inkrement und ein Vergleich. Die Zahl der Iterationen m ist abhängig vom Startwert s und dem Inkrement. Wird jeweils 1 addiert, ergibt sich m = max{0, m-s}, und damit insgesamt 2*(m+1) Schritte.

 

[JavaUndC-Prog]

Dann würde mich mal interessieren, wie du das allgemein notieren würdest, wenn es um die Anzahl der Schritte geht, ich mach mal vor was ich meine:

        for(int i = 1; i < n; i++) {    // N + 1 Schritte da:
            // i = 1 ist 1 Schritt,
            // i < n sind N + 1 Schritte,
            // i++ sind N Schritte 
            // --> max sind N+1
            if(j == k) {                //  1 Schritt aber N Schritte in der Schleife
                // Anweisung 1            // 1 Schritt
            }
            // Anweisung 2                // N Schritte       
        }                                // 1 + 1 + (N+1) + N + 1 + N

Mich würde das gleiche Beispiel für i = 1 mit i <=n, sowie i = 0 mit i < n oder i <=n interessieren
Es scheint hier überall andere Notationen zu geben, das verwirrt mich etwas...

 

[mihe7]

Wenn Du es als while-Schleife formulierst, wird es deutlicher:

int i = 1; // 1 Schritt
while (i < n) { // Vergleich wird n-mal wiederholt, da zu Beginn i == 1 gilt
    if (j == k) {  // Vergleich wird (n-1)-mal wiederholt
        // wie oft die Anweisungen ausgeführt werden, hängt von der Bedingung j == k ab
    }
    i++; // wird (n-1)-mal wiederholt
}

Es scheint hier überall andere Notationen zu geben, das verwirrt mich etwas...

Das hatten wir erst in einem anderen Thread. Der Punkt ist, dass die exakte Schrittzahl in der Regel nicht interessiert, weil am Ende die Zeitkomplexität bestimmt wird und "ein Schritt" sowieso nur eine Abstraktion ist. Ob Du zur Bestimmung der Komplexität nun die Initialisierung dazuzählst oder nicht, spielt keine Rolle.

Nachtrag:

Mich würde das gleiche Beispiel für i = 1 mit i <=n, sowie i = 0 mit i < n oder i <=n interessieren

Hier erhöht sich einfach die Anzahl um 1, falls i mit 0 oder auf i<=n geprüft wird, bzw. um 2, falls i mit 0 initialisiert und i<=n geprüft wird.

 

[JavaUndC-Prog]

Hey, danke für deine Antwort!

Ich würde deinen Ausführungen soweit auch Zustimmen, da habe ich keinen Einwand! "Hier erhöht sich einfach die Anzahl um 1, falls i mit 0 oder auf i<=n geprüft wird, bzw. um 2, falls i mit 0 initialisiert und i<=n geprüft wird. " Sehe ich auch so!

Wie gezählt wird scheint tatsächlich sehr zu variieren... In deiner While Schleife z.B. sagst du ja auch aus, dass du n-mal wiederholst und innerhalb der Schleife die Anweisungen n-1 Mal wiederholt werden. Ich habe mir angewöhnt zu merken, dass der Schleifen Kopf einmal mehr gezählt wird, als die Anweisungen in der Schleife selbst. Auch zähle ich den Schleifen Kopf mit n+1 wohingegen ich das in der Schleife mit n zähle. Wahrscheinlich mündet das darin, dass man je nach Zählart am Ende eben bsp. 7n+3 oder 3n + 5 zählt, hierbei interessiert dann aber eigentlich nur dass es in O(n) liegt. Trotzdem wäre es sehr schön, wenn das vereinheitlicht würde...

 

[mihe7]

Trotzdem wäre es sehr schön, wenn das vereinheitlicht würde...

Je nach Sichtweise ist das schwierig bzw. bereits vereinheitlicht.

Beispielsweise haben wir i++ als einen Schritt gezählt, es wären aber eher zwei, nämlich eine Addition und eine Zuweisung.

Der "Schritt" ist also bereits eine Abstraktion und die Frage ist, wovon man abstrahiert. In der Theorie ist das einfach, da arbeitet man mit klar definierten, einfachen und idealisierten Modellen. Für Hochsprachen gilt das nicht und so wird aus einem i++ ein Schritt, obwohl es zwei wären.

Die Frage ist jetzt, ob bzw. warum man an der Stelle schon aufhören soll, zu abstrahieren. Letztlich können wir für "i++" einen Schritt zählen, weil die Zeit konstant ist. Ein i++ hat also die gleiche Komplexität wie ein i = 1. Wir können also die Initialisierung auch noch dazu nehmen, dann haben wir für Initialisierung und i++ einen Schritt und schon ändert sich die ganze Zählerei.

Vereinheitlicht ist diese insofern, als man Komplexität "zählt", zum Beispiel so:

int i = 1; // O(1)
while (i < n) { // O(n)
    if (j == k) {  // O(1)
        // wie oft die Anweisungen ausgeführt werden, hängt von der Bedingung j == k ab
    }
    i++; // O(1)
}

Macht insgesamt: O(n) - ganz egal, ob i nun 1 oder 0 oder -50 war.

Noch deutlicher wird es, wenn es um Algorithmen geht, die externe Daten verarbeiten. Da spielen dann (fast immer) nur noch solche Schritte eine Rolle, die auf den externen Datenträger zugreifen. Würde man die CPU-Schritte dazunehmen, ergäbe sich ein ggf. völlig falsches Bild.

 

[LimDul]

Hinzu kommt, man zählt hier Äpfelbäume, aber verarbeitet werden hinterher Äpfel. Zwar entspricht ein Apfelbaum im großen und ganzen immer ungefähr einer gleichen Zahl Äpfel, aber nie exakt. Ob ich etwas nun als ein oder zwei Bäume zähle ist am Ende egal.

In dem Beispiel hier werden Anweisungen im Java Code gezählt. Bevor die ausgeführt werden, passiert noch:
* Umwandlung in Byte-Code (ggf. mit Optimierungen)
* Beim Ausführen umwandeln in Maschinencode mit on the fly Optimierungen je nach Virtueller Maschine und Konfiguration dieser
* Der Prozessor wiederum optimiert mit seine Pipelines da auch noch mal rum.

Sprich, ob man jetzt für gewisse Dinge 1 oder 2 Schritte zählt - am Ende kann man nicht seriös beantworten ob und was das wirklich für Auswirkungen auf die echte Laufzeit hat. Damit ist die Diskussion hier rein akademisch und eine Vereinheitlichung bringt halt nix (genauso wenig wie es sinnvoll ist allgemeingültig festzulegen, ein Apfelbaum hat 97 Äpfel). Man sollte es für die Dinge die man selber betrachtet immer gleich betrachten, um eine Vergleichbarkeit herzustellen - aber eine Vergleichbarkeit darüber hinaus ist halt eben nicht sinnvoll.