Hallo Leute,

ich möchte den Rechenaufwand für einen bestimmten Algorithmus abschätzen, und hoffe daß ihr mir dabei helfen könnt.


Zunächst mal ein vereinfachtes Beispiel:
Wenn ich wissen möchte wie viele Möglichkeiten es gibt um n Objekte in einer Reihe anzuordnen, so errechne ich das ja mit n!, richtig?

also bei 5 Objekten gäbe es dann 5! = 120 Möglichkeiten


Wenn man eine Liste mit n Objekten hätte geht es also im wesentlichen darum, daß nach dem platzieren eines Objektes noch n-1 Objekte übrig sind. Die Länge der Liste verringert sich also nach jedem Schritt um 1.


soweit so gut...
mein Problem ist leider etwas komplizierter

ich habe n Muster, die in einer Reihe angeordnet werden sollen, wobei es für jedes Muster aber nicht n-1 sondern m mögliche Nachfolger gibt. Außerdem verringert sich die Länge der Liste nicht um 1, sondern um k.

n ist festgelegt, m und k sind aber von Muster zu Muster unterschiedlich, so daß nur Durchschnittswerte bekannt sind.


Wie kann ich die Anzahl der möglichen Kombinationen anhand dieser Werte abschätzen?


Falls euch das zu theoretisch ist, dürft ihr natürlich auch gerne irgendein Zahlenbeispiel nutzen, z.B. 100 Muster mit jeweils durchschnittlich 125 möglichen Nachfolgern (ja, m kann größer sein als n, muss aber nicht), wobei in jedem Schritt vielleicht ca. 3 Muster wegfallen.


Irgendwelche Ideen?


PS:
nein, es ist definitiv nicht möglich einfach alle Kombinationen zu berechnen und diese dann zu zählen, denn selbst 100 Muster (im "einfachen" Fall also 9*10^157 Kombinationen!!) sind noch ein sehr harmloses Beispiel, es können genausogut auch 1000 oder sogar 10000 Muster sein.