如何解决T(n)的递归= 2 * T(n / 3)+ 3/2 * T(n / 4)+ 5 * T(n / 2)+ Theta(n ^ 2),p = 2 ,574359

如何解决T(n)的递归= 2 * T(n / 3)+ 3/2 * T(n / 4)+ 5 * T(n / 2)+ Theta(n ^ 2),p = 2 ,574359 我不知道如何解决如此复杂的复发。

评论
  • 深深小安
    深深小安 回复

    您可以找到如下所示的上限:

    T(n) <= (2 + 3/2 + 5) * T(n/2) + Theta(n^2) = 8.5 T(n/2) + Theta(n^2)
    

    And using master theorem, you can say T(n) = O(n^{log(8.5)) ~ O(n^{3.09}).

    Also, you can use akra-bazzi theorem. First, we need to solve the following equation

    2 * (1/3)^p + 3/2 (1/4)^p + 5 * (1/2)^p = 1
    

    After solving, we know that p ~ 2.57.