【java】这个执行频率是怎么算的？

看到一段有关于算法分析的代码，带着注释：

public class ThreeSum
{
public static int count(int[]a)
{
// 统计和为0的元组数量
int N = a.length;
int cnt = 0;
for (int i =0;i<n;i++)    //1
for(int j=i+1;k<n;j++)  //执行频率N
for(int k =j+1;k<n;k++) //执行频率略等于n^2/2
if(a[i]+a[j]+a[k]==0)//执行频率略等于n^3/6
cnt++;
return cnt;
}
public static void main(String[]args)
{
int [] a = In.readInts(args[0]);
StdOut.println(count(a));
}
}

代码干的事情就是获取一组数字然后去找三个和为0的元组数量。想问的是这个执行频率是怎么计算的？
拿这部分代码说事：

        for (int i =0;i<n;i++)    //1；这里为什么是1？我觉得应该是N啊
for(int j=i+1;k<n;j++)  //执行频率N；这里应该是N^2
for(int k =j+1;k<n;k++) //执行频率略等于N^2/2；这里应该是N^3，话说为什么要/2？
if(a[i]+a[j]+a[k]==0)//执行频率略等于N^3/6；无法理解。为什么在这里是N^3/6，而且/6是怎么来的？
cnt++;

回答

for (int i =0;i<n;i++)    //1
            for(int j=i+1;j<n;j++)  //执行频率N
                for(int k =j+1;k<n;k++) //执行频率略等于n^2/2

你可以这样来看，如下：
n=1，第一个for循环执行1次，第二个for循环执行0次，第三个for循环不执行，共执行1次。
n=2，第一个for循环执行2次，第二个for循环执行1次，第三个for循环不执行，共执行3次。
n=3，第一个for循环执行3次，第二个for循环执行2次，第三个for循环执行1次，共执行6次。
.....
依次类推：
你看这个就是前n项和的求和公式嘛：（1+n）*n/2 = n^2/2

这注释应该是从外到内求值计算.

for(i=0; i<n; i++)//执行1次,指该循环执行一次
{//循环体内执行n次
}

定理1:
前n项和

【java】这个执行频率是怎么算的？
定理2:

【java】这个执行频率是怎么算的？
推演通用公式:

【java】这个执行频率是怎么算的？

for (int i =0;i<n;i++)    //1指循环体执行一次
    for(int j=i+1;k<n;j++)  //N指该语句执行N次
        for(int k =j+1;k<n;k++) //n^2/2:前N项和的定理1
            if(a[i]+a[j]+a[k]==0)//n^3/6:1/2(n^2)中的n^2的前n项和为n^3/3再乘以1/2
                cnt++;

以上是 【java】这个执行频率是怎么算的？ 的全部内容， 来源链接： utcz.com/a/75618.html

回到顶部