计算时间复杂度

Question

有人可以用下面的代码的时间复杂度帮助：

for(i = 0; i <= n; i++) 
{ 
    for(j = 0; j <= i; j++) 
     { 
     for(k = 2; k <= n; k = k^2) 
       print("") 
     } 

的A/C给我的第一个循环运行N次，第2次会为（1 + 2 + 3上运行。 ..n）倍，第三次loglogn次.. 但我不知道答案。

Answer 1

我们从内部开始工作。考虑最内层循环：

for(k = 2; k <= n; k = k^2) 
    print("") 

print("")执行多少次迭代？首先请注意n是恒定的。 k假定什么序列值？

iter | k 
-------- 
    1 | 2 
    2 | 4 
    3 | 16 
    4 | 256 

我们可能会在几个方面找到这方面的公式。我用猜测和证明得到iter = log(log(k)) + 1。由于如果该值已经大于n，则循环将不会执行下一次迭代，因此为n执行的迭代总数为floor(log(log(n)) + 1)。我们可以用几个值来检查这个值，以确保我们得到了正确的结果。对于n = 2，我们得到一个正确的迭代。对于n = 5，我们得到两个。等等。

下一级确实是i + 1迭代，其中i从0变化到n。因此，我们必须计算总和1, 2, ..., n + 1，这将给我们最外层和中层循环的总迭代次数：这个总和是(n + 1)(n + 2)/2我们必须乘以内层循环的代价才能得到答案(n + 1)(n + 2)(log(log(n)) + 1)/2以获得总成本的片段。扩展中增长最快的术语是n^2 log(log(n))，所以这通常是渐近复杂性。