Wie lässt sich laufzeit komplexität backtracking algorithmen bestimmen

Hm, Backtracking arbeit nach dem Prinzip der Tiefensuche. Damit ergibt sich die Laufzeit daraus, dass im schlechtesten Fall alle Pfade des Baumes durchsucht werden müssen. Wenn alle Pfade endlich sind, so lässt sich die Laufzeit wie folgt bestimmen. Angenommen, der Baum hat eine maximal Pfadlänge von n und an jedem Knoten eine maximale verzeigung von m , dann berechnet sich die Laufzeit als 1 + m + m^2 +. + m^n = \sum_{i=0}^{n} Die Formel oben kann man sich recht einfach vorstellen, wenn man von einer Breitensuche ausgeht. Dann gibt i in m^i an in welcher Ebene gerade gesucht wird. Da man bei der Laufzeitberechnung meistens den schlechtesten Fall betrachtet und ich mal von einem endlichen Suchbaum ausgegangen bin, ist es dann auch egal, ob man den Baum in Breitensuche oder Tiefensuche durchlaufen würde, da man doch erst am letzten Knoten sein richtiges Ergebniss findet. Mit ober Formel folgt nach einer weiteren Abschätzung dass ein Backtrackalgorithmus eine Laufzeit von O also eine exponetielle Laufzeit hat, was schon ziehmlich übel ist, wenn man nach einer effektiven Lösung sucht. Die letzte Abschätzung gewinnt man übrigens daraus, dass \sum_{i=0}^{n-1} < m^n also \sum_{i=0}^{n} < 2m^n. Der Faktor 2 spielt aber keine Rolle demgegenüber, dass die Laufzeit exponentiell ist und wird von daher in der Schreibweise mit dem O nicht mehr angegeben. So hoffe, dass es damit etwas klar geworden ist und ich durch meine Antwort, die doch nen bischen unstruckturiert ist, keine noch größere Verwirrung gestifftet habe.