Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by gammatester,
11. Jun 2010
Vielleicht sollten wir uns erst einmal einigen, was unter Algorithmus zu verstehen ist. Es geistern hier "Algorithmus", "Algorithmen-Basis", "Problem-Stellung" usw durcheinander.
Und natürlich ist es sinnvoll, den "Apfel"-Algorithmus mit exponentieller Laufzeit mit dem "Birnen"-Algorithmus mit logaritmischer Laufzeit zu vergleichen, uns sei's nur darum, umherauszufinden welcher ein...
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by gammatester,
11. Jun 2010
Das ist mM eine leere Ausssage, denn der Algorithmus enthält eine Beschreibung der Lösungsschritte und da steht natürlich drin, ob das ganze rekursiv oder iterativ ist. Wenn dem nicht so wäre, hättest Du eine unvollständige Beschreibung mithin gar keinen keinen Algorithmus.
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by gammatester,
10. Jun 2010
Na Logo, und bei der Gelegenheit kommt man auch sofort auf den viel besseren Algorithmus: = , ] * . Es läuft also darauf hinaus, die Potenzen der Matrix A = , ] zu berechnen. Die einfache Iteration berechnet A^n via n-facher Multiplikation und ist O(n), der verbesserte Algo berechnen A^n nach dem binären "Quadriere-und-Multipliziere"-Algorithmus und ist O(log(n)).
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by gammatester,
10. Jun 2010
Naja, ganz so einfach ist es ja auch nicht. Wenn man als (zweites Standardbeispiel neben Fakultät) die Fibonacci-Zahlen gemäß der rekursiven Definition fib(n) = fib(n-1)+fib(n-2) umsetzt:
function fib(n: int64): int64;
begin
if n=0 then fib := 0
else if n=1 then fib := 1
else fib := fib(n-1)+fib(n-2);
end;
wird man für fib(90) viel Geduld brauchen. Die iterative Lösung ist für int64...
