0
Ist n an die Macht n (i-e n^n) ein Polynom? Kann T(n) = 2T(n/2) + n^n mit der Master-Methode gelöst werden?N Macht n i-e n^n ist Polynom oder nicht? Gibt es eine polynomische Differenz zwischen n^2 und n^n?
Nein, Polynome haben konstante ganzzahlige Exponenten, Ihr Exponent ist variabel. – LutzL
Also können wir diese Frage mit Meistern Methode lösen, wenn ja welcher Fall ist das? –
Nein, das geht nicht. Aber Sie erhalten 'T (n)/n = T (n/2)/(n/2) + n^(n-1)', das leicht iteriert werden kann und 'n^(n-1)' deutlich dominiert Die folgenden Ausdrücke '(n/2)^(n/2-1), (n/4)^(n/4-1)' in der Summe, also im schlimmsten Fall erhalten Sie T (n) = O (log (n) * n^n) 'und mit einigen besseren Argumenten vielleicht auch 'T (n) = O (n^n)'. – LutzL