Lösungen finden, um eine Wiederholung: T (N) = 2 T (N/4 + √ N) + (√10) N

Question

Während eine komplexe Rekursionsgleichung wie dies T(N) = 2 T(N/4 + √N) + (√10) N ;T(1) = 1

Lösung Ich habe versucht, einige Veränderungen von Variablen zu machen um es einfach zu machen und es durch Hauptsatz zu lösen, aber ich scheiterte, so nehme ich die dominante, so wird es sein: T(N) = 2 T(N/4) + (√10) N so ist es T(N)=Θ(N). Ist das wahr oder nicht?

Answer 1

Der Versuch, die Rekursion aufzurollen oder eine Substitution zu machen, hat mich nirgends verlassen. Also das einzige, was ich tun konnte, ist zu sehen, dass für jede ausreichend große n (über 64). Sie können beliebig viele (nicht nur 8) wählen, größer als 4.

So können Sie am Ende mit

Lösung dieses mit master's theorem Sie sehen, dass es mit im ersten Fall fällt.

Daher ist die Lösung Θ(N), die das gleiche ist, wie Sie sich gefragt haben.