如何找到以下函数的时间复杂度{Big-Oh}？
function(int n) {
for (int i = 0; i < n; i++){
for (int j = i; j < i*i; j++){
if (j%i == 0){
for(int k = 0; k < j; k++){
printf(" * ");
}
}
}
}
}
答案是O（n ^ 5），但我不知道如何找到它。
我认为复杂度为O（n ^ 5）。
function(int n) {
for (int i = 0; i < n; i++){ // N, max value of i is n
for (int j = i; j < i*i; j++){ // N^2, max value of j is n*n
if (j%i == 0){
for(int k = 0; k < j; k++){ // N^2, max value of k is n*n
printf(" * ");
}
}
}
}
}
第一个循环是N。第二个循环，j的最大值是i * i => n * n，所以它是n ^ 2。第三循环，k的最大值为j，为n * n，因此n ^ 2。所以n * n ^ 2 * n ^ 2是n ^ 5
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句