T(n) ={ 2T(n/2) + n^2 when n is even and T(n) = 2T(n/2) + n^3 when n is odd
我分别解决了这个问题，如果n是偶数，则得到theta(n^2)的解，如果n是奇数，则从master定理的情况3得到theta(n^3)的解。但我不应该单独解决这个问题。
如何一起解决这样的递归关系？T(n) ={ 2T(n/2) + n^2 when n is even and T(n) = 2T(n/2) + n^3 when n is odd
它是由主定理来解决的还是不适用于主定理？
请帮帮我。
最佳答案
假设某个整数n = 2^k，那么k等于n然后你可以应用主方法的偶数部分的复发。并获得100...00。
现在假设还有theta(n^2)不在最重要的位，例如1因此，在递归树中至少有一个级别，所有节点加起来都是100100..00，这样就得到n^3 * constant。
因此，如果theta(n^3)是2的幂，则答案是theta(n^2)，否则答案是n但是如果我们第一次遇到奇数，它等于一个基本情况，那么它可能不是立方的。
在和Kelalaka聊了一会儿之后，我发现如果第一个theta(n^3)是n中右边的1-th，那么如果k，我们就不再关心n。它仍然k > (2/3)(1/lg 2)lg n。
关于algorithm - 使用Master方法求解递归关系->当n为偶数时，T(n)= 2T(n/2)+ n ^ 2;当n为奇数时，T(n)= 2T(n/2)+ n ^ 3，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52598607/