很難找到嵌套的時間複雜度爲環

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] 

我希望這有助於。