很难找到嵌套的时间复杂度为环

Question

所以我一直在尝试使用下面的算法来找出大哦复杂：

for (i = 1; i ≤ n;i + +) 
    for (j = 0; j < n; j = j + i) 
      print(Array[j]); 

有人告诉我，最佳的方式将使用求和是代表，我知道它可以用某种形式表现出来，我真的不知道从哪里开始。我可以看到外部循环迭代n次，但内部循环是让我感到满意的。我希望能在这里向正确的方向推动，而不是回答。

Answer 1

如果在两个for循环中扩展总和数。在数组索引应如下所示

（0,1,2，...，N-1），（0,2,4，...，N-1），（0,3 ，6,9- .... N-1）.....（0，N/2），（0）

如果我们观察到的第一个括号具有ñ，第二个有在最坏情况下n/2等等，直到最后一个括号有。
求和所以总数可被写为

求和= SUM（从i = 1到n）[N/I]

尝试解决求和与你会得到总和数

Answer 2

让我们按照您的建议使用求和，以获得更多的分析/代数方法。

首先，只考虑：

for (i = 1; i <= n; i++) 
    //some O(1) operation 

这很简单，因为VAR i取整数值的所有范围从1到n。 我们可以表达这种循环用下面的总和：

现在，只考虑：

for (j = 0; j < n; j = j + k) 
    //some O(1) operation 

其中k为常数正整数期限（如1，2，3，... 。或等），和k <= n

在这种情况下无功i不取整数值的所有的范围从0到n-1。例如，让k=2，那么我们就可以代表什么如下图回事：

你在黑色看到的是可能的整数区间，什么是红色代表实际的整数值var i需要。如您所见，var i在奇数上“跳跃”以达到n-1，因此在这种情况下（当k=2）只有偶数。

作为结果，当k=2，复杂度是由求和给出：

通常，类似的方法可以为任意k来完成。特别要注意的是，当k倾向于n时，复杂度将趋于下降。

对于我们的目的，我们可以重写循环：

for (j = 0; j < n; j = j + k) 

由于：

for (j = 0; j < n/k-1; j++) 

都具有相同的复杂性。

最后，考虑：

for (i = 1; i <= n; i++) 
    for (j = 0; j < n; j = j + i) 
      //some O(1) operation 

在内部循环，我们有i之前扮演相同的角色我们k。这意味着将在每个可能的值i内执行内循环，范围为1到n。

重写为：

for (i = 1; i <= n; i++) 
    for (j = 0; j < n/k-1; j++) 
      //some O(1) operation 

因此，复杂性由以下两个嵌套求和给出：

首先，启动与内求和（右侧的一个），评价：

注意，我意外地将var名称从i更改为x，但这并不重要。

我们在这里得到了和另一张海报完全相同的结果。

现在，如果你只是扩大了最后求和结果是：

现在你有括号什么n次谐波数，不要与谐波系列混淆。这是离散数学（和其他领域）中有趣的数字。

这可以表示为：

注意，从这个分析就可以得到一个渐近紧约束。

BTW：你可以在这个link

语法检查的最后一个等式为：

Sum[Sum[1, {j, 0, (n/i)-1}], {i, 1, n}]=Sum[n/x, {x, 1, n}]=n*Sum[1/x, {x, 1, n}]=n*(1+1/2+1/3+...+1/n)=n*HarmonicNumber[n] 

我希望这有助于。