Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by jfheins,
13. Jun 2010
Das ist schön, das habe ich nämlich immer wieder bezweifelt.
Richtig. Das liegt daran, dass sich für Fibonacci die iterative Problemlösung besser eignet. Das heißt aber nicht dass Iteration allgemein und immer besser ist, sondern bei diesem Problem. Ich hatte das Gefühl, du verallgemeinerst das Beispiel. Siehe auch:
Was negierst du? Du hast doch oben selbst gesagt, dass du verstanden...
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by jfheins,
12. Jun 2010
Wir drehen uns im Kreis :mrgreen:
Bei Fibonacci habe ich dir eine rekursive Implementierung mit gleicher Komplexität gezeigt, die du wegen der verringerten Verständlichkeit (zu recht) abgelehnt hast. (Fibonacci ist eben ein Problem, dass man am besten per iteration löst)
Bei den Türmen von Hanoi habe ich dir gezeigt, dass rekursive Implementierungen bei gleicher Komplexität übersichtlicher...
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by jfheins,
12. Jun 2010
Ist unmöglich, da das Komplexitätsverhalten vom Algorithmus (also der Art der Problemlösung) und nicht von der Implementierung des Algorithmus (rekursiv/iterativ) abhängt. Du meinst schon das mit der Groß-O-Notation, oder? Denn ein rekursiver Quicksort und ein iterativer Quicksort haben beide eine Laufzeit von n*log(n) im Schnitt.
Das "nachzuweisen" ist trivial.
Als Gegenbeispiel führe...
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by jfheins,
11. Jun 2010
Keine Angst, die Hardware ist nicht schuld. Du bist schuld.
Das rekursive ist ein schlechterer Algorithmus, und damit klar unterlegen. Das hat nichts mit rekursion vs. iteration zu tun, sondern mit guter vs. schlechter Algorithmus.
Benutze einen Algorithmus aus Post #59 oder Post #59 und es sollte schneller laufen.
Genausogut kann ich einen rekursiven Quicksort gegen einen iterativen...
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by jfheins,
11. Jun 2010
Ich hätte auch noch eine rekursive Version auf Lager, die ohne das zusätzliche Feld auskommt:private uint fib(uint n)
{
if (n == 0)
return 0;
else
return fib(n, 1, 0);
}
private uint fib(uint n, uint x, uint y)
{
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by jfheins,
11. Jun 2010
Ihr habt mich missverstanden.
Bubblesort kann man Rekursiv oder Iterativ implementieren. (Standardvorgehensweise ist zwar iterativ, aber die äußere Schleife kann man ja auch als rekursion implementieren)
Wenn einem jetzt das Sortieren zu langsam geht, kann man natürlich die Implementierung anpassen, rekursion gegen Iteration testen und gucken was schneller läuft.
Viel mehr Gewinn macht man...
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by jfheins,
11. Jun 2010
Also was Geschwindigkeitsoptimiereung angeht halte ich mich an diese Rangliste:
(absteigend nach Wichtigkeit)
1. verwendeter Algorithmus
2. Art der Implementierung
3. Programmierspache
=> Wenn man den richtigen Algorithmus wählt, ist die Frage rekursiv/iterativ untergeordnet, solange man es vernüftig macht.