0

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

为此，我添加了三个变量icnt和。jcntkcnt

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 times\n",icnt);
        System.out.printf("j loop=%d times\n",jcnt);
        System.out.printf("k loop=%d times\n",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. 外部 for 循环（i=0 到 < N）

    这执行N次数，所以对于N=100，计数将是100

  2. 内循环(j=i+1 to < 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个

    IE，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

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

4

1 回答 1

1

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

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

于 2013-08-12T14:07:35.457 回答