循环的时间复杂度

内循环执行时外循环执行n次？所以总的时间是n *。

我是否需要学习总结，如果是，那么任何书都要参考？循环的时间复杂度

for(int i=1;i<=n;i++) 
    for(int j=1;j<=n;j+=i) 
    printf("*");

来源

2016-08-20 srbh

'printf（）'运行多少次，给定一个特定的值'n'？这是这对嵌套循环的时间复杂性。 –

@OllieJones所以你说的是一个给定的值k，时间复杂度是O（k）。让我们说n = 5，内部循环执行5次i = 1，迭代i到2，内部循环执行3次，现在i = 3内循环执行2次，i = 4内循环执行2次。它因我而异。 – srbh

我认为它会打印楼层（n/1）+楼层（n/2）+ ... +楼层（n/n）次。 – mm759

我相信那个时间的复杂性是O(n*log(n))。这是为什么：

让我们选择一些任意的自然数i，看看这个给定的i内循环需要多少步骤。对于这个我，你从j = 1到j < = n，并跳到我之间。所以基本上你正在做这个求和许多步骤：

summation = 1 + (1+i) + (1+2i) + ... (1+ki)

其中k是最大的整数，1 +き< = N。也就是说，k是步数，这就是我们想要解决的问题。那么我们可以解决在平等导致k <= (n-1)/i因此k = ⌊(n-1)/i⌋。也就是说，k是(n-1)/i的floor函数/整数除法。由于我们正在处理时间复杂性，所以这个底线函数并不重要，所以我们将简单地说出k = n/i。这是内循环对于给定的i所采取的步骤数。所以我们基本上需要将所有这些添加到i = 1到i < = n。

所以numsteps将是另外：

numsteps = n/1 + n/2 + n/3 + ... n/n 
     = n(1 + 1/2 + 1/3 + ... 1+n)

所以我们需要找到的1 + 1/2 +的总和...... 1/N来完成这一点。实际上这笔款项并没有很好的关闭形式，但大约是ln(n)。你可以阅读更多关于这个here。自integral from 1 to n of 1/x is ln(n)以来，您也可以猜测这个。再次，由于我们正在处理时间复杂性，我们可以用ln（n）来表示它的复杂性。因此我们有：

numsteps = n(ln(n))

所以时间复杂度是O(n*log(n))。

编辑：我的坏，我正在计算总和：P

来源

2016-08-20 12:45:41 gowrath

这个问题可以通过检查来逼近：

n = 16 

i | j values   | # terms 
1 | 1, 2, ..., 16 | n 
2 | 1, 3, 5, ..., 16 | n/2 
.. | ..    | n/3 
16 | 16    | n/n

在上述表中，i是外环值，并且j values显示内部循环的迭代。通过检查，我们可以看到循环将采取n * (1 + 1/2 + 1/3 + ... + 1/n)步骤。这是一个有界的谐波系列。如this Math Stack Exchange article所示，上述表达式在n方面没有关闭形式。但是，如this SO article所示，存在O(n*ln(n))的上限。

因此，您的两个循环的运行时间为O(n*ln(n))。

来源

2016-08-20 12:18:53

循环的时间复杂度

回答

相关问题