recursion - 递归函数的时间复杂度

Question

我有一个具有时间复杂度的递归函数 f(n)

O(f(n)) = O(组合(n, n/2) * f(n/2)^2)

其中combination(a, b) 表示b 之上的nuber a 组合。

我试图简化它，但没有足够的数学技能。我唯一发现的是

组合(n,n/2) = 2^n * (gamma(n/2 + 1/2)/(sqrt(1/2) * gamma(n/2 + 1)))

Answer 1

我已经在 satck 交换的这个线程中解决了它：

https://math.stackexchange.com/questions/2642848/time-complexicity-of-recursive-function?noredirect=1#comment5458208_2642848

Answer 2

我没有计算复杂性的经验，但这在我看来是有规律的n!。至少用于计算特殊情况n=2^i。用整数combination(n, n/2)等于n!/((n/2)!)^2。

f(2^i) = (2^i)! / ((2^(i-1))!)^2 * f(2^(i-1))^2
       = (2^i)! / ((2^(i-1))!)^2 * (2^(i-1))! / ((2^(i-2))!)^2)^2 * f(2^(i-2))^4
       = (2^i)! / ((2^(i-2))!)^4 * f(2^(i-2))^4
       ...
       = (2^i)! / (1!)^(2^i) = n!