循环的大O分析

Question

我必须分析这个循环,并使用Big-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),但我不确定这是否正确.有人可以帮忙吗？

编辑:抱歉哦 - > 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))

分析这笔钱不是很容易,但看一下这篇文章.使用Sterling的近似可以归属于它O(n*log(n)).因此整体复杂性是O((n/4)*2*n*log(n))= O(n^2*log(n))

Answer 2

• 就内容而言j,内循环是O(log_2(j^2))时间,但log_2(j^2)=2log(j)实际上是正弦 O(log(j)).

• 对于中间循环的每次迭代,它需要O(log(j))时间(做内循环),所以我们需要求和:

  sum {log(j)| j = 1,...,n-1} log(1)+ log(2)+ ... + log(n-1)= log((n-1)!)

自从log((n-1)!)进入以来O((n-1)log(n-1)) = O(nlogn),我们可以得出中间循环的结果O(nlogn).

• 注意,中间和内部循环都是独立的i,因此为了得到总复杂度,我们可以将n/4(外部循环的重复次数)与中间循环的复杂性相乘,得到:

  O(n/4*nlogn)= O(n ^ 2logn)

所以,这段代码的总复杂性是 O(n^2 * log(n))