关于for语句算法执行次数的问题

Question

如下代码段
for ( int i=0;i<N;i++)
for ( int j=i+1;j<N;j++)
for ( int k=j+1;k<N;k++)
if(xxxxxx)

            为什么这段算法的执行次数为 N(N-1)(N-2)/6 啊？这个/6是怎么算出来的呢？

Answer 1

可以用中学数学计算:
因为是3层循环:得到函数通式(一元3次函数): f(x)=a*x*x*x+b*x*x+c*x+d

int x=3;
int count=0;
for ( int i=0;i<x;i++)
for ( int j=i+1;j<x;j++)
for ( int k=j+1;k<x;k++)
            count++;

通过程序计算可得f(0)=0, f(1)=0,f(2)=0,f(3)=1 .有下面方程组:
d=0
a+b+c+d=0
8a+4b+2c+d=0
27a+9b+3c+d=1
对方程组进行求解得到:
a=1/6
b=-1/2
c=1/3
d=0

代入通式:f(x)=a*x*x*x+b*x*x+c*x+d可得
f(x)=x*x*x/6-x*x/2+x/3
进行分解就得到:
f(x)=x(x-1)(x-2)/6

所以这段代码的执行次数是 :N(N-1)(N-2)/6