我正试图将master定理应用于这种类型的递归：
t（n）=t（n/2）+2^n
然而，f（n）=2^n似乎不符合master定理中描述的三种情况中的任何一种，这三种情况似乎都有基n而不是基2。我怎样才能解决这种类型的复发，有人能帮忙吗谢谢。
最佳答案
如果这个定理的所有情况都不适用，那么这个定理就不能解决你的递推问题它不能解决所有的复发问题。
为了解决您的问题：通过反复替换递归情况得到的结果是T（n）=2^n+2^（n/2）+2^（n/4）++2，由于有许多项要加起来，你最终得到的结果是2^（n+1）以下，所以你总共是2^（2^n）。