java数据结构基础:算法( 二 )

通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低

但是这种方法有很大的缺陷。
事前分析估算方法

在计算机程序编制前，依据统计方法对算法进行估算

经过分析发现，一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于这些：

算法采用的策略、方法
编译产生的代码质量
问题的输入规模
机器执行指令的速度

其实你想想，这上面四条哪一条最重要？无非就是问题的输入规模。
所谓的输入规模就是输入量的大小；
我们再分析一下刚才的高斯求和；
第一种：
int sum=0; // 执行了1次int n=100; // 执行了一次for(int i=0;i<=n;i++){ // 执行了n+1次sum+=i; // 执行了n次}
第二种：
int sum=0; // 执行了一次int n=100; // 执行了1次sum=(1+n)*n/2; // 执行了1次
孰优孰劣，这下看得出来吧；
我们再看一个衍生算法：
int i;int j;int x=0;int sum=0;int n=100;for(i=1;i<=n;i++){ for(j=1;j<=n;j++){x++;sum+=x; }}
这个例子很好理解，其实也就是多循环了一百次而已，那么最后算出的次数是多少呢？n²，没错吧
我们不关心程序用的什么语言，在什么机器上执行，只关心算法。最终在分析程序的运行时间时，最重要的是把程序堪称是独立于程序设计的算法或一系列步骤。
可以从问题中得到启示，同样的规模，都是输入n，求和算法的不同，使得这个运行效率也是不同；
第一种总结出来就是f(n)=n；
第二种简单了，就是f(n)=1；第三种呢？f(n)=n²
用一张图展示一下？（来源于网络）