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:
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:
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:
Java:
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