可能有用的一个技巧是将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），符合直觉。

希望这可以帮助！