hi zusammen,

wer kann mir sagen, welche Zeitkomplexität folgendes Konstrukt hat:

FUNCTION sum (n : INTEGER) : INTEGER;

VAR s : INTEGER;

i : INTEGER;

BEGIN { sum }

s := 0;

FOR i := 1 TO n DO

s := s + i;

sum := s;

END { sum };

Mein Prof sagt, der Algo hat exponentielle Laufzeit, ich bin der Meinung (und viele andere Quellen auch), es handele sich um lineare Laufzeit.

s = s + i (konstant c) und dann n mal die schleife, also: n x c = O(n). Normalerweise irren sich profs ja nie, deswegen wollteich mal hier fragen, wie ihr das seht?

gruss

Ich würde auch sagen, dass das linear ist.

exponentiel kann das doch nur bei mehr als 2 schleifen sein (bzw. bei ner rekursion).

exponentiel kann das doch nur bei mehr als 2 schleifen sein (bzw. bei ner rekursion).

kann Euch beiden nur zustimmen.

Hat Dein Prof eine Erklärung?

die Funktion ist direkt einfach linear abhängig.

Also doppelte n = doppelte Laufzeit

direkt doppelt linear abhängig wäre z.B.

FUNCTION sum (n : INTEGER) : INTEGER;

VAR s : INTEGER;

i : INTEGER;

BEGIN { sum }

s := 0;

FOR i := 1 TO n DO

s := s + i;

FOR i := 1 TO n DO

s := s + i;

sum := s;

END { sum };

hier ist dann doppelte n = vierfache Laufzeit

exponentiell abhängig wäre:

FUNCTION sum (n : INTEGER) : INTEGER;

VAR s : INTEGER;

i : INTEGER;

BEGIN { sum }

s := 0;

FOR i := 1 TO n DO

{FOR i := 1 TO n DO

s := s + i;}

sum := s;

END { sum };

für doppeltes n = vierfache durchläufe (für dreifache n = neunfache durchläufe)

Verschachtelte Schleife.

Wobei es eben auch noch andere Möglichkeiten gibt exonentiale Abhängigkeit der Laufzeit zu erzeugen.

direkt doppelt linear abhängig wäre z.B.

FUNCTION sum (n : INTEGER) : INTEGER;

VAR s : INTEGER;

i : INTEGER;

BEGIN { sum }

s := 0;

FOR i := 1 TO n DO

s := s + i;

FOR i := 1 TO n DO

s := s + i;

sum := s;

END { sum };

hier ist dann doppelte n = vierfache Laufzeit

Nö, das ist immer noch linear. Doppeltes n, doppelte Laufzeit. Doppeltes n, vierfache Laufzeit wäre nicht linear.

exponentiell abhängig wäre:

FUNCTION sum (n : INTEGER) : INTEGER;

VAR s : INTEGER;

i : INTEGER;

BEGIN { sum }

s := 0;

FOR i := 1 TO n DO

{FOR i := 1 TO n DO

s := s + i;}

sum := s;

END { sum };

für doppeltes n = vierfache durchläufe (für dreifache n = neunfache durchläufe)

Das ist quadratisch, nicht exponentiell.

Exponentiell wäre z.B.:

FUNCTION sum (n : INTEGER) : INTEGER;

VAR s : INTEGER;

i : INTEGER;

BEGIN { sum }

s := 0;

FOR i := 1 TO pow(2, n) DO

s := s + i;

sum := s;

END { sum };

Nö, das ist immer noch linear. Doppeltes n, doppelte Laufzeit. Doppeltes n, vierfache Laufzeit wäre nicht linear.

Das ist quadratisch, nicht exponentiell.

Ok bei exponentiell war ich mir nicht ganzsicher.

aber 2 schleifen mit gleichem n hintereinander sind und bleiben linear.

deoppeltes n = vierfache Laufzeit

dreifaches n = sechsfache laufzeit

vierfaches n = achtfache laufzeit

Das ist in meinen Augen linear?

aber 2 schleifen mit gleichem n hintereinander sind und bleiben linear.

Richtig, aber was du da beschreibst, ist nicht linear.

deoppeltes n = vierfache Laufzeit

dreifaches n = sechsfache laufzeit

vierfaches n = achtfache laufzeit

Das ist in meinen Augen linear?

Das widerspricht sich selbst.

Stell dir vor, du verdoppelst n zweimal.

Nach "doppeltes n = vierfache Laufzeit" bedeutet das 4*4=16fache Laufzeit.

Nach "vierfaches n = achtfache Laufzeit" bedeutet das 8fache Laufzeit.

Passt nicht

aehm. Jetzt hast du nen Knoten drin.

Wenn du n zweimal verdoppelst.

Musst du die Laufzeit auch nur verdoppeln!

Rechne doch mal.

Die For schleife braucht bei 10n = 10s. Also bei 20n = 20s. Da sie linear abhängig ist.

Wenn ich nun 2 FOR Schleifen nacheinander abarbeite. (Beide tun das gleiche)

Dann bei 10n = 20s und bei 20n = 40s.

Bei 2 Schleifen hintereinander ändert sich also nur die Steigung der Geraden.

aehm. Jetzt hast du nen Knoten drin.

Wenn du n zweimal verdoppelst.

Musst du die Laufzeit auch nur verdoppeln!

Du hattest geschrieben, dass sich bei zwei Schleifen und doppeltem n die Laufzeit vervierfachen würde.

Bei 2 Schleifen hintereinander ändert sich also nur die Steigung der Geraden.

Ja. Trotzdem bleibt es bei: Doppeltes n, doppelte Laufzeit. Auch bei 2 Schleifen.

aehm. *rotwerd*

jep ich hab immer an die 1te Anweisung mit 1 Schleife gedacht und die als Laufzeitursprung genommen.

Jep ok dann is jett klar.