Zeitkomplexität

[noplan]

Hallo.

Ich möchte von folgendem Codeschnipsel die Zeitkomplexität für Tf(0), Tf(3), Tf(21) bestimmen, also für n=0, n=3 und n=21:

long f(int n) {
	long result ;
	if(n < 0)
		result = -1;
	else {
		result = 1;
	for(int i=0; i < n; i++) {
		int j = i+1;
		result = result * j;
		}
	}
	return result ;
}

Meine Ergebnisse sind:

Tf(0) = 10
Tf(3) = 20
Tf(21) = 92

Kann das vielleicht jemand bestätigen?! 🙂 Und funktioniert so die Bestimmung der Zeitkomplexität, oder habe ich noch irgendetwas vergessen (ist mein erster Versuch)? Danke für Tipps 🙂

 

[Final_Striker]

Ich denke die Komplexität ist O(n).

 

[XHelp]

best-case wäre O(1) und worst-case wäre O(n). Kommt aber darauf an, was du alles berücksichtigen musst, denn die Laufzeit von m+1 Rechnung ist in der Binärdarstellung auch schon O(log_2(m)).

 

[noplan]

edit: Es geht in meiner Aufgabe wohl nur ums Zählen, d.h. jeder Schritt (Deklaration, Zuweisung .... ) zählt 1.

Nach dieser Definition.

Meine Frage nun: Habe ich für die einzelnen Werte für n richtig gezählt? So wie ich das im Code sehe, wird das erste if in Zeile 3 für n=0, n=3 und n=21 nie betreten.

 

[XHelp]

Wie kommst du denn bei 0 auf 10? Die for-Schleife wird nie betreten, also bleiben nur noch:

1. long result ;
2. Auswertung der if
3. result = 1;
4. Auswertung der For-Bedingung
5. return result;

 

[noplan]

Danke, ich hab nochmal nachgezählt. Einmal müsste die for-Schleife doch betreten werden, wobei int i = 0 eins zählt und i < n auch eins. Danach wird die for-Schleife beendet.

Würde Tf(0) = 6 machen.

 

[XHelp]

Die For-Bedingung wird zwar ausgewertet, aber die For-Schleife nicht betreten:

0<0

wird nicht erfüllt