计算递归关系 T(n) = sqrt(n * T(sqrt(n)) + n)
Calculating the Recurrence Relation T(n) = sqrt(n * T(sqrt(n)) + n)
我认为这个递归的复杂度是 O(n^2/3)` 通过改变变量和归纳。但我不确定。这个解决方案正确吗？
我们知道：
T(n) = sqrt(n) * sqrt(T(sqrt(n)) + 1)
因此：
T(n) < sqrt(n) * sqrt(T(sqrt(n)) + T(sqrt(n)))
1 替换为 T(sqrt(n))。所以，
T(n) < sqrt(2) * sqrt(n) * sqrt(T(sqrt(n))
现在，要找到上限，我们需要解决以下循环关系：
G(n) = sqrt(2n) * sqrt(G(sqrt(n))
为了解决这个问题，我们需要扩展它（假设n = 2^{2^k}和T(1) = 1）：
G(n) = (2n)^{1/2} * (2n)^{1/8} * (2n)^{1/32} * ... * (2n)^(1/2^k) =>
G(n) = (2n)^{1/2 + 1/8 + 1/32 + ... + 1/2^k} =
如果我们从 1/2 + 1/8 + 1/32 + ... + 1/2^k 中取出一个因子 1/2，我们将得到 1/2 * (1 + 1/4 + 1/8 + ... + 1/2^{k-1})。
正如我们所知，1 + 1/4 + 1/8 + ... + 1/2^{k-1} 是一个比率为 1/4 的几何级数，它在无穷大处等于 4/3。因此 G(n) = Theta(n^{2/3}) 和 T(n) = O(n^{2/3}).
请注意，作为 sqrt(n) * sqrt(T(sqrt(n)) < T(n)，我们可以显示类似于之前的情况 T(n) = Omega(n^{2/3})。意思是T(n) = Theta(n^{2/3})。
T(n) = sqrt(n*T(sqrt(n)) + n)
我们将两边都取 2 的次方：
[T(n)]^2 = n*T(sqrt(n)) + n
两边除n:
{[T(n)]^2 / n} = T(sqrt(n) + 1
令m等于log(n)因此，n将等于2^m
{[T(2^m)]^2 / 2^m} = T(sqrt(2^m) + 1
我们将定义一个新函数S(m) = {[T(2^m)]^2 / 2^m}
S(m) = T(m/2) + 1
根据母校定理等于 θ(log(m)) = θ(log(log(n)))
所以我们知道：
{[T(n)]^2 / n} = θ(log(log(n)))
两边乘以n得到：
[T(n)]^2] = θ(n*log(log(n)))
因此，
T(n) = θ(sqrt(n*log(log(n))))
这是一个引人入胜的递归式，它 不是 求解 Θ(n)。相反，它似乎解决了 Θ(n2/3).
为了给出为什么这不太可能是 Θ(n) 的直觉，让我们假设我们正在处理一个非常非常大的 n 值。然后因为
T(n) = (nT(√n) + n)1/2
假设 T(√n) ≈ √n，我们会得到
T(n) = (n√n + n)1/2
= (n3/2 + n)1/2
≈ n3/4.
换句话说，假设 T(n) = Θ(n) 会随着 n 变大而给出不同的 T(n) 值。
另一方面，假设 T(n) = Θ(n2/3)。然后同样的计算给我们
T(n) = (nT(n) + n)1/2
= (n · n2/3 + n)1/2
≈ (n4/3)1/2
= n2/3,
与自身一致
为了验证这一点，我编写了一个简短的程序，在给定不同输入的情况下打印出不同的 T(n) 值并绘制结果。这是我写的 T(n) 的版本：
double T(double n) {
if (n <= 2) return n;
return sqrt(n * T(sqrt(n)) + n);
}
我决定使用 2 作为基本情况，因为反复求平方根永远不会让 n 降为 1。我还决定使用实值参数而不是离散整数值只是为了使数学更容易。
如果绘制 T(n) 的值，您会得到这条曲线：
.
这看起来不像我期望的线性图。为了弄清楚这是什么，我将其绘制在 log/log 图上，该图具有很好的 属性 所有多项式函数都转换为斜率等于指数的直线。结果如下：
我咨询了我的 Handy Neighborhood Regression Software 并要求它确定这条线的斜率。这是它返回的内容：
Slope: 0.653170918815869
R2: 0.999942627574643
非常 拟合得很好，0.653 的斜率非常接近 2/3。所以这是支持递归求解 Θ(n2/3).
的更多经验证据
现在剩下要做的就是计算数学。我们将使用一系列替换来解决此重复问题。
首先，我通常不太喜欢以这种递归方式使用指数的方式来处理指数，所以让我们记录一下双方的对数。 （在整个说明中，我将使用 lg n 表示 log2 n）。
lg T(n) = lg (nT(√n) + n)1/2
= (1/2) lg (nT(√n) + n)
= (1/2) lg(T(√n) + 1) + (1/2)lg n
≈ (1/2) lg T(√n) + (1/2) lg n
现在，让我们定义 S(n) = lg T(n)。那么我们有
S(n) = lg T(n)
≈ (1/2) lg T(√ n) + (1/2) lg n
= (1/2) S(√ n) + (1/2) lg n
虽然我们仍然遇到每次递归缩小的问题，但使用起来要容易得多。为了解决这个问题，让我们再做一个替换，这是在处理这些类型的表达式时相当常见的替换。让我们定义 R(n) = S(2n)。然后我们有那个
R(n) = S(2n)
≈ (1/2)S(√2n) + (1/2) lg 2n
= (1/2)S(2n/2) + (1/2) n
= (1/2) R(n / 2) + (1/2) n
太棒了！现在剩下要做的就是求解 R(n).
现在，这里有一个小问题。我们可以立即使用主定理得出 R(n) = Θ(n) 的结论。问题是仅仅知道 R(n) = Θ(n) 并不能让我们确定 T(n) 是什么。具体来说，假设我们只知道 R(n) = Θ(n)。那么我们可以说
S(n) = S(2lg n) = R(lg n) = Θ(log n)
得到 S(n) = Θ(log n)。然而，当我们试图根据 S(n) 求解 T(n) 时，我们会遇到困难。具体来说，我们知道
T(n) = 2S(n) = 2Θ(log n),
但我们不能由此得出 T(n) = Θ(n)。原因是 Θ(log n) 中的隐藏系数在这里很重要。具体来说，如果 S(n) = k lg n，那么我们有
2k lg n = 2lg nk = nk,
所以对数的首项系数将最终决定多项式的指数。因此，在求解R时，我们需要确定线性项的精确系数，即转化为S的对数项的精确系数。
所以让我们跳回 R(n)，我们知道它是
R(n) ≈ (1/2) R(n/2) + (1/2)n.
如果我们重复几次，我们会看到这个模式：
R(n) ≈ (1/2) R(n/2) + (1/2)n
≈ (1/2)((1/2) R(n/4) + (1/4)n) + (1/2)n
≈ (1/4)R(n/4) + (1/8)n + (1/2)n
≈ (1/4)((1/2)R(n/8) + n/8) + (1/8)n + (1/2)n
≈ (1/8)R(n/8) + (1/32)n + (1/8)n + (1/2)n.
模式似乎是，在 k 次迭代之后，我们得到
R(n) ≈ (1/2k)R(n/2k) + n(1/2 + 1/8 + 1/32 + 1/128 + ... + 1/22k+1).
这意味着我们应该查看总和
(1/2) + (1/8) + (1/32) + (1/128) + ...
这是
(1/2)(1 + 1/4 + 1/16 + 1/64 + ... )
作为几何级数的总和，求解为
(1/2)(4/3)
= 2/3.
嘿，看！这是我们之前讨论的 2/3。这意味着 R(n) 计算出大约 (2/3)n + c 对于某个常数 c 取决于递归的基本情况。因此，我们看到
T(n) = 2S(n)
= 2S(2lg n)
= 2R(lg n)
≈ 2(2/3)lg n + c
= 2lg n2/3 + c
= 2c 2lg n2/3
= 2c n2/3
= Θ(n2/3)
这与之前的理论预测值和经验观察值相符。
这是一个非常有趣的问题，我承认我对答案感到惊讶！不过，我有点紧张，因为从
出发时我可能错过了一些东西
lg T(n) = (1/2) lg (T(√n) + 1) + (1/2) lg n
至
lg T(n) ≈ (1/2) lg T(√ n) + (1/2) lg n.
有可能这个 +1 术语实际上将一些我不认识的其他术语引入了循环。例如，结果是否出现 O(log log n) 项？ That wouldn't surprise me，假设我们有一个缩小平方根的递归。但是，我已经进行了一些简单的数据探索，但我没有在其中看到任何看起来涉及双日志的条款。
希望对您有所帮助！
我认为这个递归的复杂度是 O(n^2/3)` 通过改变变量和归纳。但我不确定。这个解决方案正确吗？
我们知道：
T(n) = sqrt(n) * sqrt(T(sqrt(n)) + 1)
因此：
T(n) < sqrt(n) * sqrt(T(sqrt(n)) + T(sqrt(n)))
1 替换为 T(sqrt(n))。所以，
T(n) < sqrt(2) * sqrt(n) * sqrt(T(sqrt(n))
现在，要找到上限，我们需要解决以下循环关系：
G(n) = sqrt(2n) * sqrt(G(sqrt(n))
为了解决这个问题，我们需要扩展它（假设n = 2^{2^k}和T(1) = 1）：
G(n) = (2n)^{1/2} * (2n)^{1/8} * (2n)^{1/32} * ... * (2n)^(1/2^k) =>
G(n) = (2n)^{1/2 + 1/8 + 1/32 + ... + 1/2^k} =
如果我们从 1/2 + 1/8 + 1/32 + ... + 1/2^k 中取出一个因子 1/2，我们将得到 1/2 * (1 + 1/4 + 1/8 + ... + 1/2^{k-1})。
正如我们所知，1 + 1/4 + 1/8 + ... + 1/2^{k-1} 是一个比率为 1/4 的几何级数，它在无穷大处等于 4/3。因此 G(n) = Theta(n^{2/3}) 和 T(n) = O(n^{2/3}).
请注意，作为 sqrt(n) * sqrt(T(sqrt(n)) < T(n)，我们可以显示类似于之前的情况 T(n) = Omega(n^{2/3})。意思是T(n) = Theta(n^{2/3})。
T(n) = sqrt(n*T(sqrt(n)) + n)
我们将两边都取 2 的次方：
[T(n)]^2 = n*T(sqrt(n)) + n
两边除n:
{[T(n)]^2 / n} = T(sqrt(n) + 1
令m等于log(n)因此，n将等于2^m
{[T(2^m)]^2 / 2^m} = T(sqrt(2^m) + 1
我们将定义一个新函数S(m) = {[T(2^m)]^2 / 2^m}
S(m) = T(m/2) + 1
根据母校定理等于 θ(log(m)) = θ(log(log(n)))
所以我们知道：
{[T(n)]^2 / n} = θ(log(log(n)))
两边乘以n得到：
[T(n)]^2] = θ(n*log(log(n)))
因此，
T(n) = θ(sqrt(n*log(log(n))))
这是一个引人入胜的递归式，它 不是 求解 Θ(n)。相反，它似乎解决了 Θ(n2/3).
为了给出为什么这不太可能是 Θ(n) 的直觉，让我们假设我们正在处理一个非常非常大的 n 值。然后因为
T(n) = (nT(√n) + n)1/2
假设 T(√n) ≈ √n，我们会得到
T(n) = (n√n + n)1/2
= (n3/2 + n)1/2
≈ n3/4.
换句话说，假设 T(n) = Θ(n) 会随着 n 变大而给出不同的 T(n) 值。
另一方面，假设 T(n) = Θ(n2/3)。然后同样的计算给我们
T(n) = (nT(n) + n)1/2
= (n · n2/3 + n)1/2
≈ (n4/3)1/2
= n2/3,
与自身一致
为了验证这一点，我编写了一个简短的程序，在给定不同输入的情况下打印出不同的 T(n) 值并绘制结果。这是我写的 T(n) 的版本：
double T(double n) {
if (n <= 2) return n;
return sqrt(n * T(sqrt(n)) + n);
}
我决定使用 2 作为基本情况，因为反复求平方根永远不会让 n 降为 1。我还决定使用实值参数而不是离散整数值只是为了使数学更容易。
如果绘制 T(n) 的值，您会得到这条曲线：
这看起来不像我期望的线性图。为了弄清楚这是什么，我将其绘制在 log/log 图上，该图具有很好的 属性 所有多项式函数都转换为斜率等于指数的直线。结果如下：
我咨询了我的 Handy Neighborhood Regression Software 并要求它确定这条线的斜率。这是它返回的内容：
Slope: 0.653170918815869
R2: 0.999942627574643
非常 拟合得很好，0.653 的斜率非常接近 2/3。所以这是支持递归求解 Θ(n2/3).
的更多经验证据现在剩下要做的就是计算数学。我们将使用一系列替换来解决此重复问题。
首先，我通常不太喜欢以这种递归方式使用指数的方式来处理指数，所以让我们记录一下双方的对数。 （在整个说明中，我将使用 lg n 表示 log2 n）。
lg T(n) = lg (nT(√n) + n)1/2
= (1/2) lg (nT(√n) + n)
= (1/2) lg(T(√n) + 1) + (1/2)lg n
≈ (1/2) lg T(√n) + (1/2) lg n
现在，让我们定义 S(n) = lg T(n)。那么我们有
S(n) = lg T(n)
≈ (1/2) lg T(√ n) + (1/2) lg n
= (1/2) S(√ n) + (1/2) lg n
虽然我们仍然遇到每次递归缩小的问题，但使用起来要容易得多。为了解决这个问题，让我们再做一个替换，这是在处理这些类型的表达式时相当常见的替换。让我们定义 R(n) = S(2n)。然后我们有那个
R(n) = S(2n)
≈ (1/2)S(√2n) + (1/2) lg 2n
= (1/2)S(2n/2) + (1/2) n
= (1/2) R(n / 2) + (1/2) n
太棒了！现在剩下要做的就是求解 R(n).
现在，这里有一个小问题。我们可以立即使用主定理得出 R(n) = Θ(n) 的结论。问题是仅仅知道 R(n) = Θ(n) 并不能让我们确定 T(n) 是什么。具体来说，假设我们只知道 R(n) = Θ(n)。那么我们可以说
S(n) = S(2lg n) = R(lg n) = Θ(log n)
得到 S(n) = Θ(log n)。然而，当我们试图根据 S(n) 求解 T(n) 时，我们会遇到困难。具体来说，我们知道
T(n) = 2S(n) = 2Θ(log n),
但我们不能由此得出 T(n) = Θ(n)。原因是 Θ(log n) 中的隐藏系数在这里很重要。具体来说，如果 S(n) = k lg n，那么我们有
2k lg n = 2lg nk = nk,
所以对数的首项系数将最终决定多项式的指数。因此，在求解R时，我们需要确定线性项的精确系数，即转化为S的对数项的精确系数。
所以让我们跳回 R(n)，我们知道它是
R(n) ≈ (1/2) R(n/2) + (1/2)n.
如果我们重复几次，我们会看到这个模式：
R(n) ≈ (1/2) R(n/2) + (1/2)n
≈ (1/2)((1/2) R(n/4) + (1/4)n) + (1/2)n
≈ (1/4)R(n/4) + (1/8)n + (1/2)n
≈ (1/4)((1/2)R(n/8) + n/8) + (1/8)n + (1/2)n
≈ (1/8)R(n/8) + (1/32)n + (1/8)n + (1/2)n.
模式似乎是，在 k 次迭代之后，我们得到
R(n) ≈ (1/2k)R(n/2k) + n(1/2 + 1/8 + 1/32 + 1/128 + ... + 1/22k+1).
这意味着我们应该查看总和
(1/2) + (1/8) + (1/32) + (1/128) + ...
这是
(1/2)(1 + 1/4 + 1/16 + 1/64 + ... )
作为几何级数的总和，求解为
(1/2)(4/3)
= 2/3.
嘿，看！这是我们之前讨论的 2/3。这意味着 R(n) 计算出大约 (2/3)n + c 对于某个常数 c 取决于递归的基本情况。因此，我们看到
T(n) = 2S(n)
= 2S(2lg n)
= 2R(lg n)
≈ 2(2/3)lg n + c
= 2lg n2/3 + c
= 2c 2lg n2/3
= 2c n2/3
= Θ(n2/3)
这与之前的理论预测值和经验观察值相符。
这是一个非常有趣的问题，我承认我对答案感到惊讶！不过，我有点紧张，因为从
出发时我可能错过了一些东西lg T(n) = (1/2) lg (T(√n) + 1) + (1/2) lg n
至
lg T(n) ≈ (1/2) lg T(√ n) + (1/2) lg n.
有可能这个 +1 术语实际上将一些我不认识的其他术语引入了循环。例如，结果是否出现 O(log log n) 项？ That wouldn't surprise me，假设我们有一个缩小平方根的递归。但是，我已经进行了一些简单的数据探索，但我没有在其中看到任何看起来涉及双日志的条款。
希望对您有所帮助！