Zum Inhalt springen

Empfohlene Beiträge

Geschrieben

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

Geschrieben

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.

Geschrieben
  Enno schrieb:
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.
  Enno schrieb:
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 };

Geschrieben
  Klotzkopp schrieb:
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? :)

Geschrieben
  Enno schrieb:
aber 2 schleifen mit gleichem n hintereinander sind und bleiben linear.
Richtig, aber was du da beschreibst, ist nicht linear.
  Enno schrieb:
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 ;)

Geschrieben

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.

Geschrieben
  Enno schrieb:
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. ;)
  Enno schrieb:
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.

Dein Kommentar

Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.

Gast
Auf dieses Thema antworten...

×   Du hast formatierten Text eingefügt.   Formatierung wiederherstellen

  Nur 75 Emojis sind erlaubt.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Editor leeren

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.

Fachinformatiker.de, 2024 by SE Internet Services

fidelogo_small.png

Schicke uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Weiterlesen  

Fachinformatiker.de App

Download on the App Store
Get it on Google Play

Kontakt

Hier werben?
Oder sende eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...