递归函数的时间复杂度

Question

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

O(f(n)) = O(combination(n, n/2) * f(n/2)^2)

其中 combination(a, b) 表示组合编号 a 在 b 之上。

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

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

Answer 1

我没有计算复杂性的经验，但在我看来这很正常 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!

Answer 2

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

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

递归函数的时间复杂度

Time complexicity of recursive function

recursion

combinatorics

time-complexity

gamma-function