Ich schrieb einen rekursiven Algorithmus, der in Θ(n) läuft.Rezidivrelation mit Variable ausgedrückt in Form von n
Eine der Rekursionsgleichungen für n > 0 ist T(n) = T(v) + T(n - 1 - v) + c wo c eine Konstante ist und v ist eine Variable, die Werte in dem festen Bereich n > v > 0 haben kann.
Wie kann ich diese Gleichung weiter lösen oder richtig vereinfachen?
einfach wiederholt die nicht konstanten Begriff erweitern:
Die Serie endet, wenn:
Das bedeutet, dass 
, wie der Begriff T(v) wird mit dem Nenner aufheben in N.
Berücksichtigt diese Lösung die Tatsache, dass 'v' mit jedem rekursiven Aufruf dieses Typs variieren kann (abhängig von der Topologie des Unterbaums, auf dem der Aufruf ausgeführt wird)? Oder nimmt es an, dass "v" während einer einzigen Ausführung des Algorithmus eine Konstante ist? – George
Ja, da der Nenner dann die Summe aller 'Vi's ist und die Summe von' T (Vi) 'den Nenner _still_löst. –
In den Kommentaren beschrieben Sie das Verhalten Ihres Algorithmus wie folgt: es macht eine konstante Menge an Arbeit auf einem leeren Baum und ansonsten eine konstante Menge an Arbeit, dann verarbeitet die linken und rechten Unterbäume rekursiv. Anstatt die Laufzeit mit einer Wiederholungsbeziehung wie der von Ihnen beschriebenen zu beschreiben, können Sie die Laufzeit auf andere Weise berücksichtigen: Die geleistete Arbeit ist direkt proportional zur Anzahl der Knoten in der Struktur, da Sie jede Arbeitseinheit berechnen können zu einem bestimmten Knoten. Die Gesamtlaufzeit ist daher O (n).
Nichts für ungut, aber du sagst das Offensichtliche. Meine Aufgabe ist es, eine vollständige theoretische Analyse des Algorithmus zu schreiben, also brauche ich die Wiederholungsbeziehung, um die zeitliche Komplexität zu beschreiben (und zu beweisen). – George
Beachten Sie, dass eine Rekursionsbeziehung nur eine Möglichkeit darstellt, um eine vollständige theoretische Analyse eines Ergebnisses zu erhalten. Nachdem ich eine Zeitlang Algorithmen studiert und viele Artikel gelesen habe, bin ich relativ zuversichtlich, dass ein Argument wie dieses vollkommen in Ordnung sein wird. – templatetypedef
Wenn der Wert von 'v' sich dem Mittelpunkt des Bereichs' (0, n) 'nähert, ist die Komplexität 'O (log (n))' und wenn der Wert von 'v' an der Ecke von ist In diesem Bereich wird die Komplexität "O (n)" sein. – Shubham
Ohne mehr über v zu wissen, ist es nicht möglich, diese Wiederholung zu beheben. Was weißt du über v? Woher kam diese Wiederholung? – templatetypedef
@templatetypedef Der Algorithmus wird zur Verarbeitung binärer Bäume verwendet. Die rohe, nicht vereinfachte Gleichung wäre T (n) = T (nL-1) + T (nR-1) + c, wobei "L" der linke Unterbaum (verwurzelt am linken Kindknoten) und " R 'ist der rechte Teilbaum (der am rechten Kindknoten verwurzelt ist) des Wurzelknotens, der gerade verarbeitet wird. Da "R = n-1-L" und "L = n-1-R" (wobei "n" die Gesamtzahl von Knoten in dem Unterbaum ist und "1" für den Wurzelknoten steht), kann die Gleichung vereinfacht werden als T (n) = T (nL-1) + T (n- (n-1-L) -1) + c = T (nL-1) + T (L) + c ', was äquivalent ist zu "T (n) = T (R) + T (n-1-R) + c". – George