Ich habe eine Diskussion mit meinem Freund, wir hatten gestern eine Prüfung. Ich sagte, es könnte nicht, er sagte, es wäre Fall 1. Wahrscheinlich hat er recht, aber ich kann nicht verstehen, warum. Vielen Dank im Voraus.kann t (n) = 2t (n/2) + n^0,5/logn mit dem Hauptsatz gelöst werden?
Für jeden Wert von n größer als 1 hat n^(0,5/log n) einen konstanten Wert von exp (0,5). Dies kann sehr leicht bewiesen werden:
x = n^(0.5/log n)
log(x) = (log n) * 0.5/(log n) = 0.5
=> x = exp(0.5) = 1.64872...
Als Ergebnis kann der zweite Term des Ausdrucks als Konstante behandelt werden. Mit einem konstanten zweiten Term entspricht Ihre Formel t(n) = 2t(n/2) + 1, die Komplexität O (n) hat.
Und ja, dein Freund hat Recht. Dies entspricht case 1, wobei der Wert von c in f (n) ∈ 0 (n^c) gleich Null ist.
n^(0.5/log n) ist eine Konstante (= exp (0.5)) für alle n! = 1 –
Entschuldigung, ich habe nicht verstanden, was Sie geschrieben haben. – Timur