algorithm - 关系的时间复杂度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)还是错的？

最佳答案

不，您不能使用Mater定理解决它。

您需要使用Akra–Bazzi method来解决它，这是众所周知的主定理的更简洁的概括。

主定理假定子问题的大小相等。

主定理涉及

形式的递归关系



我在这里没有得出解决方案的步骤，因此您可以进行解决。如果您在解决问题时还有其他问题，请在下面评论。祝你好运...

关于algorithm - 关系的时间复杂度T(n)= T(n-1)+ T(n/2)+ n，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30402313/