给出以下代码-:
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j = j+i)
{
//Do something
}
我知道外循环运行 N
次,并且内部循环运行大约 log(N)
次。这是因为在 i
的每次迭代中, j
运行ceil(N)
, ceil(N/2)
, ceil(N/4)
次等等。这只是粗略的计算一下,可以猜测时间复杂度肯定是 O(N log(N))
.
我如何从数学上证明这一点?
我知道对于 i<sup>th</sup>
迭代,j
增加ceil(N/2<sup>(i - 1)</sup>)
.
最佳答案
对于 i 的每个值,内循环的迭代总数为
i = 1: j = 1, 2, 3 ..., n ---> total iterations = n
i = 2: j = 1, 3, 5 ..., n ---> total iterations = n/2 if 2 divides n or one less otherwise
i = 3: j = 1, 4, 7 ..., n ---> total iterations = n/3 if 3 divides n or one less otherwise
...
i = m: j = 1, 1 + m, ... , n ---> total iterations ~ n/m
...
1
因此总迭代次数大约为(n + n/2 + n/3 ... + 1)
。
这个总和是Harmonic Series其值约为 ln(n) + C
,因此总迭代次数约为 n ln(n)
,并且由于所有对数都通过常数相关,因此迭代次数将为 O(nlogn)
。
关于big-o - 此代码的大 O 时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22587042/