我是否需要学习总结，如果可以，那么有什么书可以参考吗？
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j+=i)
printf("*");
我相信那是时间上的复杂性O(n*log(n))。原因如下：
让我们选择一个任意的自然数i，并查看给定i的内循环要执行多少步。为此，我要从j = 1跳到j <= n，而i介于两者之间。因此，基本上，您正在执行许多步骤的汇总：
summation = 1 + (1+i) + (1+2i) + ... (1+ki)
其中k是使1 + ki <= n的最大整数。也就是说，k是步骤数，这是我们要解决的问题。那么我们可以在平等的解决对于k产生k <= (n-1)/i，因此k = ⌊(n-1)/i⌋。也就是说，k是的下限函数/整数除法(n-1)/i。由于我们要处理时间复杂性，因此该下限函数并不重要，因此我们只是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)。您可以在此处了解更多信息。您也可以自以来猜测到这一点integral from 1 to n of 1/x is ln(n)。同样，由于我们要处理时间复杂度，因此我们可以仅使用ln（n）来表示其复杂度。因此，我们有：
numsteps = n(ln(n))
因此，时间复杂度为O(n*log(n))。
编辑：我不好，我正在计算总和：P
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句