我这里有一个函数,我可以看到它是 O(N^2)。但是,我想弄清楚每行到底使用了多少步/计算。
void hi(int n){
for (int i=1; i <= n; i++) { //line 1
for (int k = i; k <= n; k++) { //line 2
puts("hi"); //line 3
}
}
}
对于第 1 行,我相信它是 1+(N+1)+1。
第 2 行和第 3 行应该都是 sum(i=1 到 n)(3i+2),但我不知道如何计算。这个总和是从哪里来的?
最佳答案
外部 for
语句执行一次……尽管它迭代了 n
次(由于开始条件、结束条件和更新部分)。这是“第 1 行”。
内部的 for
语句将在外部循环的每次迭代中执行一次。外层循环迭代n
次,因此内部for
语句执行n
次。这是“第 2 行”。
"hi"
将为内循环的每次迭代写入一次。对于外循环的每次迭代,内循环将迭代 n-i+1
次(产生 i
的值)。这意味着打印 "hi"
的次数是 n
(对于 i == 1
)+ n-1
(对于 i == 2
)+ .... 1
(对于 i==n
)。将它们相加,等于 n*(n+1)/2
次。这是“第 3 行”。
关于c - 算法每行中的计算/步骤数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39824545/