c++.de :: Fakultät in logarithmischer Lauftzeit berechnen

CBR-Racer Mitglied 09:58:47 13.12.2003 Titel:

das würde dann ja nicht der Aufgabenstellung entsprechen

Jester Moderator 10:51:04 13.12.2003 Titel:

Gregor schrieb:

Alles vorher ausrechnen und in nem Array speichern.
[...],ist das IMHO immer noch eine vollkommen legitime, richtige und natürliche Lösung. Es ist sogar die beste Lösung.

Für einen Programmiere/Softwareentwickler ja, für einen Informatiker nicht. Begründung: s.o.

MfG Jester

PoRcUpInE Mitglied 11:44:57 13.12.2003 Titel:

viel ist die repetitive form schneller:

fac(n) = facrep(n,1)

facrep(n,x) = if n > 0 then facrep(n-1, x*n) else x

Aber obs reicht, probiers mal aus!

Unregistrierter

Wo ist die Begründung? Ich seh sie nicht.

Gregor Moderator 12:40:00 13.12.2003 Titel:

Jester schrieb:

Für einen Programmiere/Softwareentwickler ja, für einen Informatiker nicht. Begründung: s.o.

Doch, selbstverständlich ist das auch für einen Informatiker die beste Lösung. Es ist der effizienteste Algorithmus für den gewünschten Wertebereich. Warum sollte sich ein Informatiker mit etwas minderwertigem abfinden? Damit es "mathematischer" aussieht? ...BTW: Ich habe sogar ein Skript aus einer Informatikvorlesung, in dem genau dieses Beispiel vorkommt. Dort wird auch eindeutig gesagt, dass dies die beste Lösung.

Du scheinst dich auf den Standpunkt zu stellen, dass man so eine Art "allgemeingültige" Lösung als Informatiker finden muss. Das ist nicht richtig. Ein Informatiker ist sich durchaus darüber im klaren, dass ein Computer, als das Werkzeug, auf dem der Algorithmus irgendwann mal läuft, Beschränkungen hat. Entsprechend beachtet er diese Beschränkungen auch bei der Konstruktion von Algorithmen. Deine Sichtweise ist eher die Sichtweise eines Mathematikers.

Zitat:

das würde dann ja nicht der Aufgabenstellung entsprechen

Wie du weiter oben an der Definition der O-Notation schon gesehen hast, ist O(1) eine Teilmenge von O(log(n)). Es entspricht also durchaus der Aufgabenstellung. Wenn ein Algorithmus eine Laufzeit von O(1) hat, dann hat er auch eine Laufzeit von O(log(n)).

Gregor Moderator 13:01:25 13.12.2003 Titel:

Jester schrieb:

Auch Sortierung läßt sich in O(1) erledigen. Einfach alle möglichen Ordnungen als Index in die Tabelle der korrekt sortierten Mengen verwenden. Jede Funktion ist über einem endlichen Definitionsbereich O(1), aber das ist hier nicht der Punkt.

Das ist wieder die Sichtweise eines Mathematikers. Völlig an der Realität vorbei! Dein Definitionsbereich ist bei einem Sortieralgorithmus vielleicht endlich, im Regelfall hat der Definitionsbereich hier aber immer noch mehr Elemente als es Atome in unserem Universum gibt. Ich möchte mal sehen, wie du das vorspeicherst.

Dieses Beispiel ist in keinster Weise mit dem hier gegebenen Problem zu vergleichen.

TGGC Mitglied 22:53:58 13.12.2003 Titel:

CBR-Racer schrieb:

also ihr werdet es kaum glauben ... also der Prof sprach mich heute an und fragte, ob ich die Aufgabe geschafft hätte ... ich sagte mit herabgesenktem Kopf nein ... fragte aber auch gleich wie man die Fakultät in logarithmischer Laufzeit berechne ... er schaute nur etwas verdutzt und fragte, ob er wirklich Fakultät gesagt hätte ... das wurde ihm dann von mehreren Leuten bestätigt ... er entschuldigte sich höflich ... was er eigentlich wollte war ein Algorithmus um die Fibonacci-Zahlen in logarithmischer Lauftzeit ...

Glaub ich sofort, war ja meine erste Vermutung ;)

Jester Moderator 01:18:08 14.12.2003 Titel:

Gregor schrieb:

Das ist wieder die Sichtweise eines Mathematikers.

Davon distanziere ich mich entschieden!
Der Informatiker sucht das beste allgemeine Lösungsverfahren für ein Problem... und dieses stelle Dein Vorschlage nunmal nicht dar!

MfG Jester

WebFritzi Mitglied 07:51:58 14.12.2003 Titel:

Jester schrieb:

Davon distanziere ich mich entschieden!

YEAH! Verteidige unsere Stellung!