解决复发:T(n)= T(n ^(1/2))+Θ(lg lg n)

Question

开始学习算法.我理解如何从'常规复发'中找到theta-notation T(n) = Tf(n) + g(n).但是我对这种复发感到迷茫:问题1-2e:

T(n)= T(√n)+Θ(lg lg n)

如何选择找到theta的方法？什么,呃,这种复发是什么？我只是不太明白符号 - 内部复发的事情.

Answer 1

可能有用的一个技巧是将n转换为其他东西,例如2 ^k.如果我们这样做,你可以重写上面的内容

T(2 ^k)= T(2 ^k/2)+Θ(log log 2 ^k)

= T(2 ^k)= T(2 ^k/2)+Θ(log k)

现在这看起来像我们实际上可以解决的重现,因为我们可以将其扩展为

T(2 ^k)= T(2 ^k/2)+ log k = T(2 ^k/4)+ log(k/2)+ log k

如果我们将其扩展一次,我们就会得到

T(2 ⁱ)= T(2 ^{k/2 i})+ log k + log(k/2)+ log(k/4)+ ... + log(k/2 ⁱ)

此复发终止时2 ^{K/2 我} ≤2(比方说,在这种情况下我们达到一个基本情形),其发生在

2 ^{k/2 i} = 2

k/2 ⁱ = 1

k = 2 ⁱ

我= lg k

换句话说,如果我们可以写n = 2 ^k,那么净结果将是

T(n)= lg k + lg(k/2)+ log(k/4)+ log(k/8)+ ... 1

lg k +(lg k) - 1 +(lg k) - 2 +(lg k) - 3 + ... +(lg k) - lg k

=Θ((lg k)²)

并且因为我们知道n = 2 ^k,这意味着k =Θ(log n),所以用它代替我们得到T(n)=Θ((log log n)²).

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

这有道理吗？好吧,如果你考虑一下,log log n除了其他外,还是写出log n所需的位数.在每次迭代中,您将获取数字的平方根,这会使其表示中的位数减半.这减少了将in中的位数写出一个所需的位数.因此,第一次迭代将写出log log n位,第二次(log log n)-1,第三次(log log n) - 2等.总的来说,这个求和是Θ((log log n)²),这符合直觉.

希望这可以帮助!