complexity-theory - nT(n/2)+n 的复杂度

Question

这段代码的复杂性是多少？我知道关系是 T(n)=nT(n/2)+n

代码

void methode(int n)     
 for (int i = 1; i <= n; i++) {
   ifs1 = ifs1 + 1;
   if (n >= 1)
    methode(n / 2);
} 

标签： complexity-theory

Answer 1

这种方法有一个非常不寻常的递归关系，T(n) = n(T(n) + 1)。我相信渐近解是

T(n) ∈ Θ(n^((log2(n)+1)/2))

或格式精美：

如果您需要我更详细地说明，请告诉我。