下面代码比较小于的频率是 (N+1)(N+2)/2。
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
}
}
我认为 N+1 用于第一个循环。 (N+2)/2 怎么样?
最佳答案
在第一次迭代中,内部循环运行 N-1
次,在第二次迭代中 N-2
次等等。每次,<
再次检查操作(当条件不再成立时),因此 N + N-1 + N-2 + ... + 1
检查 <
在内部循环的所有迭代中。在外循环中,<
额外检查了N+1
次,总计 N+1 + N + ... + 1
次。该总和等于 (N+2)*(N+1)//2
.
您还可以将迭代次数可视化为(锯齿状)三角形:
#####
####
###
##
#
通常,边长为 N+1
的直角三角形面积为 (N+1)*(N+1)//2
,但由于它的连字符是“锯齿状的”,所以它是一个额外的 (N+1)//2
(是 N+1
边长为 1 的较小三角形),再次加起来为 (N+2)*(N+1)//2
关于algorithm - 小于比较算法的频率,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54805876/