 |
 |
 |
 |
 |
 |
Startseite » Forum » rekursive Funktion - Optimierung des Algorithmus
rekursive Funktion - Optimierung des Algorithmus
Universität / Fachhochschule
Sonstiges
Kombinatorische Optimierung
Tags: Alogrithmen, Kombinatorische Optimierung, Sonstiges
 
|
  |
|---|
|
Hallo zusammen Es ist zwar ein Mathematikforum hier, aber ich denke, dass Algorithmen hier dennoch hinpassen.. Ich sollte einen Algorithmus finden, der folgende Rekursionsgleichung löst: falls falls sonst Und zwar soll ich dieses Programm für mehrere vom Benutzer zu wählen) Eingaben ausführen, also für verschiedene Konstanten und das ist auch frei zu bestimmen. Mit relativ kleinen Datenmengen funktioniert mein Programm relativ gut, fehlerfrei. Doch bei grossen Mengen ist mein Algorithmus zu langsam.. Da wollte ich fragen, ob ihr eine allgemeine Lösung kennt, wie man denn rekursive Algorithmen verschnellern kann? ich habe einfach zuerst eingeben lassen, dann in einer for-Schleife jeweils und einlesen lassen und dann rekursiv eine Funktion aufgerufen. Die Konstanten habe ich global abgespeichert, als Argument übergebe ich bei der rekursiven Funktion nur . Mir ist nicht klar, wie ich das optimieren könnte.. Vielen DAnk für eure Hilfe.. Bin echt ziemlich aufgeschmissen sonst.. Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
| Hierzu passend bei OnlineMathe: Funktion (Mathematischer Grundbegriff) |
|
 |
|
Vielleicht wäre in deinem Fall ein iterativer Algorithmus schneller als dein rekursiver.
siehe . www.delphipraxis.net/13311-rekursion-oder-iteration-ist-schneller.html#post97550 |
 |
|
Vielen Vielen Dank.. Ich habe das Programm iterativ umgeschrieben und habe nun viel viel bessere Leistungen bei höheren Inputs. Dankeschön.. Ich wollte noch fragen: Gäbe es auch eine Möglichkeit, dass man versucht, aus einer rekursiven Gleichung eine explizite zu erstellen und dann das Programm "explizit" berechnet, dann hätte man ja knostante Laufzeit? |
|
|
|
Hallo Du könntest es mal hiermit versuchen. Wie man sieht, ergeben sich da ein paar Einschränkungen für . Kannst dir ja mal darüber Gedanken machen. |
|
|
|
Hallo Dann müsste sein, da die Variablen aber automatisch von einem Computerprogramm generiert werden, dürfte ich keine Ansprüche an die Variablen stellen. Kann man also sagen: Rekursiv in explizit umwandeln geht manchmal, aber eventuell mit Einschränkungen der Variablen, die vorher nicht da gewesen wären? Gibt es denn eine allgemeine Vorgehensweise, wie man eine rekursive Funktion in eine explizite umwandelt? Wir hatten schon mal so was Ähnliches gemacht. Dazu haben wir einfach mehrfach immer wieder rekursiv eingesetzt, bis wir irgendwann mal ein Muster erkannt haben und dann haben wir diese Vermutung über vollständige Induktion noch beweisen müssen. Hast du diese Gleichung auch über dieses Verfahren gefunden? |
|
|
|
Vorab möchte ich gleich sagen, dass ich mich mit dem Thema bisher nicht groß befasst habe. Ich wusste nur unter welchem Stichwort man schauen muss, also sind meine Aussagen mit Vorsicht zu genießen! Das Thema heißt einfach Lösen von Rekursionen, in deinem Fall sind das lineare Rekursionen. Kannst ja mal danach suchen. Man geht so vor, dass man sich ein Polynom aufstellt, Nullstellen sucht und über das Lösen eines Gleichungsssystems bestimmte Koeffizienten ( und ) einstellt. Bei dem allgemeinen Fall, den ich dir aufgestellt habe, könnte es zwei Probleme geben: einmal durch Null teilen () und dann der Wurzelausdruck. Beim Wurzelausdruck könnte ich mir sogar vorstellen, dass man sogar komplexe Zahlen zulassen kann. Probier das einfach mal, also such dir eine Rekursion wo das vorkommt. Bei dem durch Null teilen weiß ich es gerade nicht. Da macht ja nur der Fall Probleme. In allen anderen Fällen sollte es klappen. Gibt es vllt Einschränkungen an ? EDIT: Komplexe Zahlen bilden keine Einschränkung. Bleibt noch das Fall . |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
976474
976410