求助化简递归函数时间复杂度：O(f(n))=O(combination(n,n/2)*f(n/2)²)

这是个很有意思的递归复杂度分析问题！我们可以一步步来拆解，先从组合数的渐近近似入手，再转化递归式来求解。

你已经用Gamma函数给出了组合数的表达式，不过对于时间复杂度分析，我们更常用斯特林近似来得到组合数的渐近上界/下界，这会更直观。斯特林公式是：
n! ≈ √(2πn) (n/e)^n

代入组合数公式C(n, n/2) = n! / [(n/2)!]^2，计算可得：

C(n, n/2) ≈ [√(2πn) (n/e)^n] / [ (√(2π(n/2)) (n/(2e))^{n/2}) )^2 ]
= [√(2πn) n^n / e^n] / [ 2π(n/2) * n^n / (2^n e^n) ]
= 2^n / √(πn/2)

所以组合数的渐近复杂度是Θ(2^n / √n)——这比Gamma函数形式更适合后续的递归分析。

原递归式是T(n) = C(n, n/2) * T(n/2)^2，这种乘积+平方的递归式直接分析比较麻烦，我们可以对两边取自然对数（底数不影响渐近结果，选自然对数方便计算），令L(n) = ln T(n)，则：

L(n) = ln C(n, n/2) + 2L(n/2)

代入组合数的渐近结果，ln C(n, n/2) = n ln2 - (1/2)ln(πn/2) + O(1)，其中O(1)是低阶常数项，所以：
L(n) = n ln2 + 2L(n/2) + O(log n)

我们用迭代法展开这个递归式（假设T(1) = 1，即L(1)=0）：

L(n) = n ln2 + 2*( (n/2)ln2 + 2L(n/4) + O(log(n/2)) ) + O(logn)
= n ln2 + n ln2 + 4L(n/4) + O(logn) + 2O(log(n/2))
= 2n ln2 + 4L(n/4) + O(logn)
...

展开到第k = log2 n层（此时n/2^k = 1），每一层的主项都是n ln2，共k项，所以主项之和是k * n ln2 = n ln2 * log2 n = n ln n（因为log2 n = ln n / ln2）。

而所有低阶的O(logn)项之和是O(n logn)，相对于主项n ln n是同阶的，所以最终：
L(n) = Θ(n log n)

因为L(n) = ln T(n)，所以T(n) = e^{Θ(n logn)}。结合斯特林公式，我们可以得到更精确的形式：
当n是2的幂时，递归式的解恰好是T(n) = n!（可以验证：T(2)=2=2!，T(4)=C(4,2)*T(2)^2=6*4=24=4!，T(8)=C(8,4)*T(4)^2=70*24²=40320=8!）。而n!的渐近行为由斯特林公式给出：
T(n) = Θ( (n/e)^n √(2πn) )

如果用大O符号简化表达，也可以写成O(n^n)，不过(n/e)^n √n是更精确的渐近界。

另外，你之前用Gamma函数推导的组合数表达式，其实和斯特林近似是一致的——Gamma函数的渐近行为就是斯特林公式，所以两者可以相互推导。

内容的提问来源于stack exchange，提问作者Stastny Jakub