时间复杂度验证
所以我有这个代码块:时间复杂度验证
int sum=0;
for (int i=1; i<n; ++i){
for (int j=1; j<i*i; ++j){
if (j%i==0){
for (int k=0; k<j; ++k){
++sum;
}
}
}
}
,我想通这有$ O(N^5)$的复杂性。我试着对此进行计时来验证,但我无法确定是否最适合使用$ n^4 $或$ n^5 $。
复杂度是n^4。 原因是,第三个将运行O(n^2)
时间而不是O(n^3)
,因为您可能已计算。 if case只会被称为(i*i)^(1/2) = O(n)
次,因为从1
到i*i
的i
的倍数数字恰好是i = O(n)
。
所以我有这个代码块:
int sum=0;
for (int i=1; i<n; ++i){
for (int j=1; j<i*i; ++j){ // O(n)
if (j%i==0){
for (int k=0; k<j; ++k){ // O(n^2)
++sum; // O(n^4)
}
}
}
}
完全重复,我不同意这种说法回答 – RSon1234
我无法遵循你的逻辑。为什么在这种情况下称为O(n)次? –
我在解释事情上很不好,让我编辑我的答案。这个if被称为外部for的每一步的O(n)次。 –
的https://*.com/questions/46562623/time-complexity-of-this-algo –