运行时间的递归方程

Question

我需要解决递归问题：

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

当我们调用 n 个元素时，我们有

log^2（n） 个动作（递归动作除外），依此类推，直到我们调用 2 个元素并且我们有 1 个动作。

如何计算 T（n） 运行时间？

Answer 1

这是

SO，这不是提出运行时问题的地方。

但是，由于它已经在这里，我将回答这个问题，并且可能会得到-5

运行时间为 O(log(n)) . 这是因为计算log^2(n)需要O(1)，所以这对运行时来说是微不足道的。 所以我们有

T(n) = T(n/2)

这是一个经典的O(log(n))