相关和条件三重for循环的时间复杂度

本文介绍了相关和条件三重for循环的时间复杂度的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 for i in xrange(1,n+1): for j in xrange(1,i*i): if j%i==0: for k in xrange(0,j): print("*")

上述算法的时间复杂度是多少?

What will be the time complexity of the above algorithm?

推荐答案

这听起来像是一个家庭作业问题，但非常有趣，因此我将大胆尝试一下.我们只计算星号的打印次数，因为它占主导地位.

It sounds like a homework problem, but is very interesting so I'll take a shot. We will just count number of times that asterisk is printed, because it dominates.

对于每个j，只有被i整除的那些对象才会触发最内层循环的执行.有多少个?好吧，在[1, i*i)范围内的是i, 2*i, 3*i, ..., (i-1)*i.让我们走得更远. k从0迭代到j，所以首先我们将进行i迭代(对于j=i)，然后是2*i(对于j=2*i)，然后是3*i ..，直到我们迭代(i-1)*i次.每个i 总共有i + 2*i + 3*i + (i-1)*i个打印星号.由于i从0到n，因此迭代总数是所有i + 2*i + 3*i + (i-1)*i的总和，其中i从0到n.让我们总结一下:

For each j, only those that are divisible by i trigger the execution of the innermost loop. How many of them are there? Well, in range [1, i*i) those are i, 2*i, 3*i, ..., (i-1)*i. Let's go further. k iterates from 0 to j, so first we will have i iterations (for j=i), then 2*i (for j=2*i), then 3*i.. until we iterate (i-1)*i times. This is a total of i + 2*i + 3*i + (i-1)*i printed asterisks for each i. Since i goes from 0 to n, total number of iterations is sum of all i + 2*i + 3*i + (i-1)*i where i goes from 0 to n. Let's sum it up:

在这里，我们多次使用公式计算第一个n个数字的总和.最终总和中的主导因素显然是k^3，并且因为第一个n-1立方和的公式为

Here we used multiple times the formula for sum of first n numbers. The factor which dominates in the final sum is obviously k^3, and since the formula for sum of first n-1 cubes is

，

总复杂度为O(n^4).