MarkHH Geschrieben 26. Januar 2009 Geschrieben 26. Januar 2009 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 Zitieren
Klotzkopp Geschrieben 27. Januar 2009 Geschrieben 27. Januar 2009 Ich würde auch sagen, dass das linear ist. Zitieren
U-- °LoneWolf° Geschrieben 27. Januar 2009 Geschrieben 27. Januar 2009 exponentiel kann das doch nur bei mehr als 2 schleifen sein (bzw. bei ner rekursion). Zitieren
VaNaTiC Geschrieben 29. Januar 2009 Geschrieben 29. Januar 2009 Zitat 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? Zitieren
Enno Geschrieben 29. Januar 2009 Geschrieben 29. Januar 2009 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. Zitieren
Klotzkopp Geschrieben 29. Januar 2009 Geschrieben 29. Januar 2009 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 LaufzeitNö, 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 }; Zitieren
Enno Geschrieben 29. Januar 2009 Geschrieben 29. Januar 2009 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? Zitieren
Klotzkopp Geschrieben 29. Januar 2009 Geschrieben 29. Januar 2009 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 Zitieren
Enno Geschrieben 29. Januar 2009 Geschrieben 29. Januar 2009 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. Zitieren
Klotzkopp Geschrieben 29. Januar 2009 Geschrieben 29. Januar 2009 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. Zitieren
Enno Geschrieben 29. Januar 2009 Geschrieben 29. Januar 2009 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. Zitieren
Empfohlene Beiträge
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.