T(n)=2T(n−−√)+logn

Question

我正在尝试寻找该递归的时间复杂度：

T(n) = 2T(n^1/2) + log n

我已经非常接近解决方案了，但是遇到了障碍。我需要解决：

n^(1/2k) = 1

以简化我的替换模式。我不是在寻找递归的答案，只是要解决k的问题。

- Waqas

---

我认为那样做并不能帮助。如果你解决了k的问题，你会得到一些令人惊恐的东西。 - harold

我投票关闭此问题，因为它是一个数学问题，而不是一个编程问题。 - Raymond Chen

Stack Overflow是一个关于编程和开发问题的网站。这个问题似乎与编程或开发无关，因此不属于讨论范围。请参阅帮助中心中的我可以在这里提问哪些话题。也许数学堆栈交换会更适合您的提问。 - jww

Answer 1

当您展开递归时，您会得到：

---

以下是同样的内容，加上了一些额外步骤：

现在使用递归的边界条件（选择数字2作为0和1没有意义），您将得到： 将k代回方程式，您将得到： 以下是使用相同思路的几个递归示例。

• T(n) = T(n^1/2) + 1
• T(n) = T(n^1/2) + O(loglog(n))

- Salvador Dali

---

先生，这是我的方法 https://i.stack.imgur.com/C2uiq.png，请帮助我继续前进。谢谢 :) - laura

@laura 我认为我的解决方案没有问题。我添加了一些中间步骤。 - Salvador Dali

是的，你说得对。非常感谢！ - laura

Answer 2

对于k，n>1的情况下，任何非零的x都有n^x>1，所以无法解决以下方程：

n^(1/2k) = 1

唯一的解法是选取一个k，使得1 / 2^k = 0，但这是不可能的。

然而，你可以解决以下方程：

n^(1/2k) = 2

首先，将两边取对数：

(1 / 2^k) lg n = lg 2 = 1

接着，将两边乘以2^k：

lg n = 2^k

最后，再次取对数：

lg lg n = k

因此，当k = lg lg n时，这个递归停止。

虽然你只要求k的值，但因为已经过去了一年，我想指出你可以进行变量替换来解决这个问题。尝试设置k = 2ⁿ。那么k = lg n，因此你的递归就是：

T(k) = 2T(k / 2) + k

这个解法（使用主定理）是T(k) = Θ(k log k)，并且使用k = lg n的事实，整个递归的解为Θ(log n log log n)。

希望这可以帮到你！

- templatetypedef

---

先生，我可以这样解决吗-：T(n) = 2T(n1/2) + log n => T(2^m)=2T(2^(m/2))+log 2^m => T(2^m)=2T(2^(m/2))+m=> 让 2^m=k => S(k)=2S(k/2)+log k - laura

接近了！如果你插入k = 2^n，当你将它表示为k的函数时，log n项会发生什么？ - templatetypedef

Answer 3

兄弟，如果这是快速排序方程：

这个问题的解决方案是 O(n*log(n))，因为现在它甚至更小了(T(n) ~ n^1/2)，对于一些N，这意味着你的复杂度小于O(n*log(n))。

尝试使用归纳法证明你的界限。

- 0x90

---

是的，我同意这将是一个好方法，因为合并是次线性的，输入大小也要小得多。然而，如果其他所有方法都失败了，我会尝试归纳法，但我只是好奇一般情况下如何解决形式为c^a^b=1的方程以求得b。我知道这涉及到使用幂恒等式的一些巧妙技巧。 - Waqas

Answer 4

以任何底数为基数的对数1，其结果都为0。

因此

n^((1/2)^k) = 1

log(n)(n^((1/2)^k)) = log(n)(1)

1/2^k = 0

log(1/2)((1/2)^k) = log(1/2)(0)

以0为基数的对数是负无穷...所以...

k = -无穷大。

我认为你应该使用一个不同于1的“最终数字”来代替n，只是这样说而已...

- Serge

---

主要是因为你永远无法一直进行平方根运算，直到1。你会发疯的。 - Serge