java - 这个执行频率是怎么算的?
巴扎黑
巴扎黑 2017-04-18 09:52:50
0
2
220

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

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++;
巴扎黑
巴扎黑

热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!