Master-Theorem kann verwendet werden, um Wiederholungsrelationen wie T(n)= aT(n/b)+f(n) zu lösen.Algorithmen: Master Theorem
Also, wenn f(n)=O(n) oder wenn f(n)=cn beide die gleichen Werte sind? kann ich Mastersatz für f(n)=cn auch verwenden?
Asumming dass c eine Konstante ist, und dass ich Ihre Frage richtig verstanden hat, wird die Lösung gleich sein sowohl für f(n) = O(n) und f(n) = cn, da cn = O(n) und damit der Master-Satz angewandt werden, um die zu Wiederholungen zu lösen.
Wenn ich die Frage richtig verstanden habe, ist f(n)=cn (wo c eine Konstante ist) in O(n); der Hauptsatz kann angewendet werden.
Konstanten wie "c" werden oft ignoriert, wenn asymptotische Beziehungen betrachtet werden. Dies ist so, weil, wenn 'n' ausreichend groß wird, die Konstante es sehr schwer macht, den Speicherverbrauch und die Laufzeit zu berechnen. Dies würde bedeuten, dass 'f (n) = n', was äquivalent zu 'f (n) = 0 ist. n) –