Ich erfrische mich ein wenig über den Hauptsatz und versuche, die Laufzeit eines Algorithmus herauszufinden, der ein Größenproblem löstn durch rekursives Lösen von 2 Teilproblemen der Größen-1 und kombinieren Sie Lösungen in konstanter Zeit.
Die Formel lautet also:
T(N) = 2T(N - 1) + O(1)
Ich bin mir aber nicht sicher, wie ich die Bedingung des Hauptsatzes formulieren kann.
Ich meine, das haben wir nichtT(N/b) so ist esb der Hauptsatzformel in diesem Fallb=N/(N-1)?
Wenn ja, seitdem offensichtlicha > b^k schon seitk=0 und istO(N^z) woherz=log2 mit Sockel von(N/N-1) Wie kann ich das verstehen? Angenommen, ich habe bisher recht?