algorithm - 循环的大 O 分析

Question

我必须分析这个循环以及其他循环，并使用大 O 表示法确定它的运行时间。

for ( int i = 0; i < n; i += 4 )
    for ( int j = 0; j < n; j++ )
        for ( int k = 1; k < j*j; k *= 2 )`

这是我目前所拥有的:

for ( int i = 0; i < n; i += 4 ) = n

---

for ( int j = 0; j < n; j++ ) = n

---

for ( int k = 1; k < j*j; k *= 2 ) = log^2 n

现在我要解决的问题是循环的最终运行时间。我最好的猜测是 O(n^2)，但是我不确定这是否正确。谁能帮忙？

编辑:对 Oh -> O 的事情感到抱歉。我的教科书用“Big-Oh”

Answer 1

首先请注意，外层循环独立于其余两个 - 它只是添加了一个 (n/4)* 乘数。我们稍后会考虑。

现在让我们考虑一下

的复杂性

for ( int j = 0; j < n; j++ )
    for ( int k = 1; k < j*j; k *= 2 )

我们有以下总和:

0 + log₂(1) + log₂(2 * 2) + ... + log₂(n*n )

值得注意的是 log₂(n^2) = 2 * log₂(n)。因此，我们将总和重构为:

2 * (0 + log₂(1) + log₂(2) + ... + log₂(n) )

要分析这个总和不是很容易，但请看一下 this post .使用 Sterling 的近似值，它属于 O(n*log(n))。因此，整体复杂度为 O((n/4)*2*n*log(n))= O(n^2*log(n))