我的功能的时间复杂度是多少？
这个问题在这里已经有了答案：
外循环运行n次。
对于每次迭代，内部循环运行n / i次。
总运行次数是：
n + n/2 + n/3 + ... + n/n
渐近地（忽略整数算术舍入），这简化为
n * (1 + 1/2 + 1/3 + ... + 1/n)
这个系列松散地收敛于n * log(n) 。
因此，复杂度是O（N.log（N）），如你所料。
第一个内部循环运行n次
第二个内部循环运行n/2次
第三个内部循环运行n/3次
..最后一个运行一次
因此n + n/2 + n/3 + ... + 1 = n(1+1/2+1/3+1/4 + ... +1/n) 。
这是n乘以谐波系列的总和，它没有一个很好的封闭形式表示。 但如这里所示，它是O(log(n)) 。 所以整体算法是O(n log(n))
作为替代，使用变量替换y = n - x然后使用Sigma符号来分析算法内部while循环的迭代次数。
上面高估了对于每个内部while循环，在n-1不是i的倍数的情况下，即其中(n-1) % i != 0情况下，迭代次数减1 。 正如我们继续进行，我们将假设(n-1)/i为的所有值的整数i ，因此高估迭代在内总数while循环，随后包括在小于或等于标志(i)下面。 我们继续进行Sigma符号分析：
我们在(ii)中已经用相关积分近似了n次谐波数。 因此，你的算法在O(n·ln(n))中渐近地运行。
离开渐近行为并研究算法的实际增长，我们可以使用@chux（参考他的答案）的精确(n,cnt) （其中cnt是内部迭代次数）对的好样本数据，并与估计值进行比较从上面开始的迭代次数，即n(1+ln(n))-ln(n) 。 很显然，估计与实际数量整齐地协调一致，请参阅下面的图表或实际数字的此片段。
最后要注意的是，如果我们在1/i以上的总和中令n->∞ ，那么所得到的序列就是无限谐波序列，它足够奇怪地发散。 后者的证明利用了这样一个事实，即在无限项的无限和中自然是无限的。 然而，在实践中，对于一个足够大但不是无限的n， ln(n)是总和的一个适当的近似值，这个差异与我们这里的渐近分析无关。
链接地址: http://www.djcxy.com/p/39341.html