如何找到的嵌套的循環

Question

什麼是嵌套循環的時間複雜度如下所示的時間複雜度：

1）

for (int i = 1; i <=n; i += 2) { 
    for (int j = 1; j <=n; j += 2) { 
     // some O(1) expressions 
    } 
} 

2）

for (int i = 1; i <=n; i += 3) { 
    for (int j = 1; j <=n; j += 3) { 
     // some O(1) expressions 
    } 
} 

一般：

for (int i = 1; i <=n; i += c) { 
    for (int j = 1; j <=n; j += c) { 
     // some O(1) expressions 
    } 
} 

這是真的嗎下列？

O(nc)

Answer 1

您的算法將執行​​迭代。我們正在分割，因爲我們每跳都跳過c個字符。請參閱：

for (var i = 0; i <= n; i = i + 1) 

將有n/1迭代

for (var i = 0; i <= n; i = i + 2) 

將有n/2迭代

_{*請注意，結果將被難倒。也就是說，如果n = 3和c = 2，將只執行一次（floor(3/2) == 1）}

所以，我們可以概括它是

 
(n/c)2 
= (n2/c2) 
= 1/c2 * n2 

記住Big O只是變化率感興趣。由於c是一個常數，因此從計算中忽略它。

所以，結果是：

O(1/c2 * n2) = O(n2)

Answer 2

對於一般情況，內部循環有O（n），外部循環有O（n）。因此，對於外部循環的每次迭代，內部循環重複n次（c對複雜度的順序無關緊要，應該被視爲1）。如果外循環迭代n次，則內循環中的迭代總數爲n * n或O（n^2）。

Answer 3

想象一下，有10把椅子（在這裏） 在一個for循環，你正在迭代所有的椅子，讓說你坐在所有的椅子上，所以總共你需要坐10次坐在所有的椅子對於給定的循環。

現在想象你坐在第一把椅子上，要求你的朋友一個接一個坐在其他椅子上，包括你的椅子，所以你的朋友總共坐在10把椅子上。 現在你選擇了第二把椅子，再次請你的朋友再次坐在每把椅子上，所以他總共要坐在10把椅子上。

同樣，您可以選擇第3，第4 ......椅子等，因此總共您的朋友必須爲您選擇的每把椅子坐上10把椅子。

10 + 10 + ... = 100倍

這相當於10^2 = 100

所以複雜性爲O（n^2），其中n是椅子的數目。