寻找以下递归式的复杂度：T(n) = T(n/2) + log(n)。

Question

我如何估算两个循环的运行时间，每个循环的运行时间都是对数级别的，如下所示：

for(int i=n; i>=0; i /= 2)
{
    for( int j=i; j>=0; j /= 2)
    {
        count++;
    }
}

我的分析：

i = n  , 1  => j = lg n  | 1+lg (n) 
i = n/2, 1  => j = lg n/2 | 1+lg (n/2)
i = 1  , 1  => j = 0      | 1

如何在这种情况下总结对数项？

- user7624559

---

您的问题标题和描述不够清晰，请详细说明并更新您的标题。 - CodeChanger

@CodeChanger 现在呢？清楚了吗？ - user7624559

太好了，现在看起来清晰明了，也可以回答了。 - CodeChanger

注意：这两个循环都是无限的... - Alex Lop.

Answer 1

i = n.      | Inner loop runs log(n) iterations.       | O(log(n))
i = n/2.    | Inner loop runs log(n/2) iterations.     | O(log(n))
i = n/4.    | Inner loop runs log(n/4) iterations.     | O(log(n))
.           |                                          |
.           |                                          |
i = log(n). | Inner loop runs log(log(n)) iterations.  | O(log(log(n)))

我们注意到什么？对于每个n，我们都会添加O(log(n))。这个递归式为T(n) = T(n/2) + log(n) + 1，可以按以下方式展开：

T(n) = log(n) + log(n/2) + log(n/4) + ... + 1
     = log(n) + [log(n)-1] + [log(n)-2] + [log(n) - 3] + .... + 1
     = log(n)*log(n) - (2 + 3 + .... log(n))
     = log(n)*log(n) - ([(2+log(n))*log(n)]/2) 
     = log(n)*log(n) - ~0.5log(n)*log(n)
     = ~0.5log(n)*log(n)

T(n) = O(log(n)*log(n))

- Tony Tannous