Zeitkomplexität eines Algorithmus

[MarkHH]

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

[Klotzkopp]

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

[U-- °LoneWolf°]

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

[VaNaTiC]

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?

[Enno]

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.

[Klotzkopp]

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 };

[Enno]

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?

[Klotzkopp]

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

[Enno]

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.

[Klotzkopp]

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.

[Enno]

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.