循環的三倍增長順序

Question

我正在練習算法的複雜性，我在網上找到了這個代碼，但我無法弄清楚它的增長順序。有任何想法嗎？

int counter= 0; 
    for (int i = 0; i*i < N; i++) 
    for (int j = 0; j*j < 4*N; j++) 
    for (int k = 0; k < N*N; k++) 
    counter++; 

Answer 1

在一個時間把它一個步驟（或在這種情況下，循環）：

1. 第一環路增量i只要它的平方比N較低，所以這必須O(sqrt N)，因爲int(sqrt(N))或int(sqrt(N)) - 1是平方值小於N的最大整數值;

2. 對於第二個循環也是如此。我們可以忽略4，因爲它是一個常數，在處理大哦符號時我們不關心這些。所以前兩個循環一起是O(sqrt N)*O(sqrt N) = O(sqrt(N)^2) = O(N)。由於循環是嵌套的，因此可以乘以複雜度，所以第二個循環將完全執行第一個循環的每個迭代;

3. 第三個循環顯然是O(N^2)，因爲k上升到了N的平方。

所以整個事情必須是O(N) * O(N^2) = O(N^3)。通常可以通過計算第一個循環的複雜性，然後第二個，然後是前兩個等來解決這樣的問題。

Answer 2

的Sqrt NX 2的Sqrt nxn的^ 2

其中給出：

，O n^3

說明：

對於第一環路，平方根二者的側面方程式

i^2 = n

對於第二個循環，平方根的等式兩邊

J（1）2 = 4N^2

第三環是直線前進。