時間複雜度混亂

程序O(n^2)以下的時間複雜程度如何？時間複雜度混亂

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

第二for環將不執行權作爲在條件j <= n，j的值將總是大於n。
檢查3點在這個link

東西看起來錯在這裏。也許他們在第一個循環中意味着'i - = c'？ – IVlad

奇數組循環 - 外部似乎正在倒計時，內部倒計時 - 由他們的條件 - 但都是增加（上）與相同的值 - 或減少如果該值爲負。你確定你在這裏得到了正確的例子嗎？ – davidbak

是@davidbak示例是正確的。我想在原始鏈接中存在打字錯誤。 –

倘若n和c爲正數，然後是第二個for循環將不會執行。

在我看來，那些for循環在該鏈接中寫入不正確。

2017-04-09 08:11:00

我認爲作者實際上意味着這裏是

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

這樣，複雜性是（1 + n/c）*（n/2c）= O(n^2)

2017-04-09 08:59:44 Hac

回答