algorithm - 算法：主定理

Question

主定理可用于解决递归关系，如 T(n)= aT(n/b)+f(n).

那么，如果f(n)=O(n)或如果f(n)=cn两个值相同？我也可以使用主定理f(n)=cn吗？

Answer 1

假设这c是一个常数，并且我正确理解了您的问题，则 和 的解决方案将是相同的f(n) = O(n)，f(n) = cn因为cn = O(n)因此可以应用主定理来解决重复问题。

Answer 2

如果我正确理解了这个问题，f(n)=cn（c常数在哪里）在O(n)；可以应用主定理。