执行频率代码分析

Question

我试图找出以下代码中某些语句的执行频率
我想检查对于给定的输入数组，每个for循环执行了多少次。

为此，我添加了三个变量icnt、jcnt和kcnt。

public class FreqCounter{
    public static void count1(int[] a){
        int N = a.length;
        int count = 0;
        int icnt = 0;
        int jcnt = 0;
        int kcnt = 0;
        for(int i=0;i<N;i++){
            icnt++;
            for(int j=i+1;j<N;j++){
                jcnt++;
                for(int k=j+1; k<N;k++){
                    kcnt++;
                }
            }
        }
        System.out.printf("i loop=%d timesn",icnt);
        System.out.printf("j loop=%d timesn",jcnt);
        System.out.printf("k loop=%d timesn",kcnt);
    }
    public static void main(String[] args) {
        int N = 100;
        int[] a =  new int[N];
        count1(a);
    }
}

我得到了以下输出

i loop=100 times
j loop=4950 times
k loop=161700 times

我试着如下分析

1. 循环的外部（i=0到<N）

   这将执行N次，因此对于N=100，计数将为100

2. 循环内部（j=i+1到<N）

   这相当于找到N个元素的组合，每次取2个

   即C(N,2) = N! /((N-2)! * 2!) = (N *(N-1))/2 = ((N^2)/2)-(N/2)

   对于N=100，这将是(100*100/2)-50 = 4950

3. 最内部循环（k=j+1到<N）

   相当于找到N个元素的组合，每次取3个

   即C(N,3) = N!/((N-3)! * 3!) = N*(N-1)*(N-2)/3! = (N^3/6)-(N^2/2)+N/3

   对于N=100，这将是100^3/6 - 100^2/2 + 100/3 = 161700

我得到了正确的值，但想知道分析（组合的东西）是否正确。（我最近才学到排列/组合的课程）。如果有人能在这个分析中添加更多内容，那将是有帮助的。

Answer 1

你的组合数学非常好，你有n个不同的元素，你需要选择3个元素的可能性数量，顺序无关紧要，没有重复。这确实是C(N,3)。

（免责声明，我在过去的几个月里是一名组合数学助教）