>有人知道如何解决这个复杂性方程吗？
T(n)=sqrt(n)T(sqrt(n))+nlogn
所以我解决了它。
这是解决方案 在此处输入图像描述
下面是递归定义：
T(1) = c
T(n) = sqrt(n) * T(sqrt(n)) + nlogn
我们可以假设分数结果向下舍入到最接近的整数。我们可以列出一些值并尝试猜测模式：
n T(n)
- ----
1 c
2 1*(c) + 2*log(2) = c + 2
4 2*(c + 2) + 4*log(4) = 2c + 12
16 4*(2c + 12) + 16*log(16) = 8c + 112
256 16*(8c + 112) + 256*log(256) = 128c + 3840
...
到目前为止，我们可以很容易地注意到 带c项的系数等于n的一半 .稍作思考，就会得出这样的结论：这一观察普遍成立。我们的其他术语是这样构建的：
2log2
2(2log2) + 4log4
4(2(2log2) + 4log4) + 16log16
16(4(2(2log2) + 4log4) + 16log16) + 256log256
...
我们可以使用对数定律将这些术语组合如下：
log(2^2)
log(2^4) + log(2^8)
log(2^16) + log(2^32) + log(2^64)
log(2^256) + log(2^512) + log(2^1024) + log(2^2192)
...
因此，第k个元素的常量是k项的总和，其中日志中的最小项是2^(2^(2^(k-1)))，而其日志中的每个后续项是前一个项的两倍。我们可以进一步使用日志定律来帮助获得封闭式解决方案：
log(2^2)
log(2^4) + 2log(2^4)
log(2^16) + 2log(2^16) + 4log(16)
log(2^256) + 2log(2^256) + 4log(2^256) + 8log(2^256)
...
我们发现可以使用最小值来表示第k项的值log(2^(2^(2^(k-1))))并计算出现次数：1、1+2、1+2+4、...这些计数形成一个闭合形式的序列 2^k - 1。因此，第k个元素的值为(2^k - 1)log(2^(2^(2^(k-1))))。
n和k的关系如下：
k n
- ---
1 2 = sqrt(2^(2^k))
2 4 = sqrt(2^(2^k))
3 16 = sqrt(2^(2^k))
4 256 = sqrt(2^(2^k))
...
So, `n = sqrt(2^(2^k))`. This means `n^2 = 2^(2^k)`, `2logn = 2^k` and finally `k = loglogn + 1`. Replacing in our formula for the constant given `k` yields:
(2^(loglogn + 1) - 1)log(2^(2^(2^((loglogn + 1)-1))))
(2logn - 1)log(2^(2^(2^(loglogn)))
(2logn - 1)log(2^n)
(2logn - 1)n
因此，不涉及c的术语是n(2logn - 1)。总之，我们有：
T(1) = c
T(n) = n(c/2 + 2logn - 1)
我们已经为您给出的递归关系的函数恢复了一个精确的闭式表达式。这样做并不总是像此示例那样简单。