algorithm - 小于比较算法的频率

Question

下面代码比较小于的频率是 (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 怎么样？

Answer 1

在第一次迭代中，内部循环运行 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