相关和条件三重for循环的时间复杂度 [英] Time complexity of dependent and conditional triple for-loop

问题描述

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).

这篇关于相关和条件三重for循环的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！