主定理计算算法成本

Question

请问有人能帮我解决这个问题吗？

T(n)=T(n^(1/2)) + theta (lg lg n)

这是我目前所做的。

设定：

m = lg n
s(m)=s(m/2) + theta (lg m)

在这里应用主定理

a=1 b=2
m^log 2 (1) = m^0 =1 

现在我卡住了。

- aneena

---

n^(1/2) = sqrt(n)，而(lg n) / 2 != sqrt(n)，因此你目前的工作似乎是错误的。你一定要使用主方法吗？ - IVlad

@IVlad lg(sqrt(n)) == lg(n)/2 == m / 2（根据定义）。这难道不正确吗？ - Asad Saeeduddin

@Asad - 是的，没错。但是原帖中有 T(sqrt(n))，我不明白他是怎么从那里得出 T(lg(sqrt(n)) = T(m / 2) 的。如果他写成了 T(lg sqrt(n)) 就没问题了。 - IVlad

@IVlad T(√n)=s(lg√n)=s(m/2). 我认为你忽略了使用s(m)=T(n)。 - Teepeemm

Answer 1

你有：

a = 1, b = 2
f(m) = Ө(lg(m))

主定理的第二种情况适用于以下情况：

f(m) = Ө(m^c * lg^k(m))

where:

c = log_b(a)

Testing this out, we have:

f(m) = Ө(lg(m)) = Ө(m^0 * lg(m)) 
-> c = 0
-> c = log_b(a) = log_2(1) = 0

所以第二种情况是适用的。因此，对于这个递归式的解决方案如下：

T(m) = Ө(m^c * lg²(m)) = Ө(lg²(m))

替换m后，我们回到

T(n) = Ө(lg²(lg(n)))

- Asad Saeeduddin

---

我认为应该是 T(m)=Ө(m^c * lg²(m)) = Ө(lg²(m))，因此 T(n)=Ө(lg²(lg(n)))。 - Teepeemm

你能再解释一下吗？也许我漏掉了什么。k是什么？ - aneena

@aneena 有三种情况。第一种情况是当 f(n) = O(n^c)，其中 c < log_b(a)。第二种情况适用于 f(n) = Ө(n^c * (lg(n))^k)，其中 c = log_b(a)（k 很重要，因为它出现在递归的解决方案中）。第三种情况适用于 n^c = O(f(n)) 或等价地说，f(n) = Ω(n^c)，其中 c > log_b(a)。这可能与您在主方法中看到的情况略有不同，因为我们在这里定义了严格的边界，而不是使用 O 来表示一切。 - Asad Saeeduddin

@Asad Ah，我误解了你的符号表示。谢谢澄清！ - templatetypedef

@aneena 这是对数项所提高的幂次。例如，如果我有 T(n) = T(n/2) + Ө(n^2*(lg(n))^3)，那么 c 就是 2，k 就是 3。 - Asad Saeeduddin

Answer 2

首先，T(n) = T(n^(1/2)) + theta(lg lg n) 可以写成：

T(2^(2^k)) = T(2^(2^(k-1))) + theta(k).

将上述方程从 k=1 到 d 进行聚合，得到 T(2^(2^d)) = theta(d^2)。令 n=2^(2^d)，我们得到 T(n) = theta( (lg lg n)^2 )。

- Eric

---

@ TAN 第二行应该是k+1吧？ - aneena

@aneena 这是平方根：(2^(2^k))^(1/2) = 2^(2^k / 2) = 2^(2^(k-1)). - Eric