小编Frz*_*zzy的帖子

我在尝试计算此代码的时间复杂度时遇到了一些问题:

function foo (int a):
    if a < 1: 
        return 1
    else:
        for i = 1 to 4:
            foo(a - 3)
        for i = 1 to 4:
            foo(a / 2)
end function

据我所知:

T(n) = 1 if n<1

T(n) = 4T(n-3) + 4T(n/2)     if n>=1

     = 4(4T(n-6) + 4T((n-3)/2))  +  4(4T(n/2 - 3) + 4T(n/4))

     ~ 4^2 (T(n-6) + T((n-3)/2) + T(n/2-3) + T(n/4))

现在,它非常复杂,因为下一个T的数量增加了2 ^ n,而且孩子也很复杂.

有没有其他方法可以解决这个问题？