adn*_*leb 7 algorithm complexity-theory recurrence time-complexity master-theorem
为了这种关系
T(n)= T(n-1)+ T(n/2)+ n
我可以先解决得到O(n ^ 2)的项(T(n-1)+ n),然后求解项T(n/2)+ O(n ^ 2)？
根据主定理,它也给出O(n ^ 2)或者它是错的？
不，你不能用母定理来解决它。
\n\n您需要使用Akra\xe2\x80\x93Bazzi 方法来解决它，这是著名的主定理的更清晰的概括。
\n\n主定理假设子问题具有相同的大小。
主定理涉及以下形式的递推关系
\n\n\nT(n) = a T(n/b) + f(n) ，其中 a>=1，b>1。
\n
我不会在这里导出解决方案的步骤，以便您解决它。如果您在解决相同问题时遇到其他问题，请在下面评论。祝你好运...
\n| 归档时间： |
|
| 查看次数： |
719 次 |
| 最近记录： |