worst-case, usw. wie genau? < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 02:12 Sa 05.11.2011 | | Autor: | Sin777 |
Hallo, wir hatten in der Vorlesung das Thema worst-case, average-case und co. Jetzt ist mal generell meine Frage, wie genau man das eigentlich nimmt. Folgende Fragen hätte ich:
Wenn die Komplexität einer Schleife berechnet wird (worst-case, best-case, average-case), so bin ich mir laut Skript nicht sicher, was ich denn alles mit einberechnen soll. Beispielsweise diese Schleife for(int i = 1; i < n; i++){sum = sum + i;}.
sum + i: ein Einheit, Zuweisung (=) eine Einheit, n-1 Schleifendurchläufe und 1 Vergleich
für den Abbruch, Zuweisung in der for-Schleife 1 Einheit => (n-1)*2 + 2.
Bei uns im Skript wird dieses +1 für den Abbruch weggelassen und auch das +1 in der Zuweisung in der for-Schleife. Auf der anderen Seite ist es aber wichtig, dass es (n-1) und nicht n Schleifendurchläufe sind. Ich bin verwirrt ... entweder man nimmt es genau oder eben nicht aber was ich nun mitzähle und was nicht scheint mir teilweise völlig wahllos.
Zählt i = i + 3 als zwei Einheiten?
Zum Thema Pseudocode: Gibt es dafür einen Standard oder macht das auch jeder wie er will?
Gruß
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 02:20 Mo 07.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:23 Mo 07.11.2011 | | Autor: | awakening |
zuweisungen und vergleiche zählt man in der regel nicht mit, nur floating point operations
@pseudocode, jeder wie er will wobei der lesbar sein sollte sonst bringt er nix...
|
|
|
|
