algorithm - 带有 if-else 语句的 for 循环的大哦

Question

我想知道为什么以下代码 O(n^4) 而不是 O(n^5) 的 Big-Oh 复杂度最严格：

int sum = 0;
for(int i=1; i<n ; i++){ //O(n)
    for(int j=1; j<i*i; j++){ // O(n^2)
        if(j%i == 0)
            for(int k=0; k<j; k++) //O(n^2)
            sum++;
    }
}

谁能帮我这个？谢谢！

标签： algorithmif-statementbig-o

Answer 1

它回到最里面的if状态。j%i == 0只对 for而言，第二个循环将运行的j = {i, 2*i, 3*i, ..., i * i}只是时间。因此，紧复杂度为。iO(i^2)O(n^4)