解决复发：T（n）= T（n ^（1/2））+Θ（lg lg n）[关闭]

开始学习算法。我知道如何从“定期重复”中找到theta记号T(n) = Tf(n) +

g(n)。但是我迷失于这种复发：问题1-2e：

T（n）= T（√n）+Θ（lg lg n）

如何选择找到theta的方法？而且，这种复发是什么？我只是不太了解循环符号。

可能有用的一个技巧是将n转换为其他值，例如2 k。如果执行此操作，则可以将以上内容重写为

T（2 k）= T（2 k / 2）+Θ（对数log 2 k）
= T（2 k）= T（2 k / 2）+Θ（log k）

现在，这看起来像是我们实际上可能能够解决的重复现象，因为我们可以将其扩展为

T（2 k）= T（2 k / 2）+对数k = T（2 k / 4）+对数（k / 2）+对数k

如果我们将其扩展到i倍，我们得到

T（2 i）= T（2 k / 2 i）+对数k +对数（k / 2）+对数（k / 4）+ … +对数（k / 2 i）

此当2复发终止K / 2 我 ≤2（比方说，在这种情况下我们达到一个基本情形），其发生在

2 k / 2 我 = 2
k / 2 我 = 1
K = 2 我
i = lg k

换句话说，如果我们可以写n = 2 k，那么最终结果将是

T（n）= lg k + lg（k / 2）+对数（k / 4）+ log（k / 8）+ … 1
lg k +（lg k）-1 +（lg k）-2 +（lg k）-3 + … +（lg k）-lg k
=Θ（（lg k）2）

并且由于我们知道n = 2 k，这意味着k =Θ（log n），因此将其代入即可得到T（n）=Θ（（log log n）2）。

这里的关键技巧是将n重写为2 k。其余的是标准技术。

这样有意义吗？好吧，如果您考虑一下，log log n就是写出log

n所需的位数。在每次迭代中，您都将取数字的平方根，这将其表示形式的位数减半。这将写出的位数减少了1。因此，第一次迭代将写出log log

n位，第二个（log log n）-1，第三个（log log n）-2，等等。总的来说，该总和为Θ（（log log n）2），符合直觉。

希望这可以帮助！