1.算法效率的度量方法

事后统计方法

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

事前分析估算方法

于是出现一款新度量算法效率的方法。

• 事前分析估算方法：在计算机程序编写前，依据统计方法对算法进行估算。
• 经过总结，我们发现有个高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

1. 算法采用的策略，方案。
2. 编译产生的代码质量。
3. 问题的输入规模。
4. 机器执行指令的速度。

• 由此可见，抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间依赖于算法的好坏和问题的输入规模。（所谓的问题输入规模是指输入量的多少）

  ---

• 第一种算法

#include <stdio.h>
int main()
{
    int sum=0，n=100;    //执行1次
    for (i = 1; i <= n; i++)   //执行了n+1次
    {
        sum += i;    //执行了n次
    }
    printf("%d", sum);
    return 0;
}

• 第二种算法：

#include <stdio.h>
int main()
{
    int sum,a,n;    //执行1次
    scanf("%d,%d",&a, &n);
    sum = (a + n) * n / 2;    //执行1次
    printf("%d", sum);
    return 0;
}

2.函数的渐进增长

判断以下两个算法A和B哪个更好？

图表分析

当n=1时，算法A1效率不如算法B1,

当n=2时，两者效率相同

**当n>2时，算法A1就开始优于算法B1了，随着n的继续增加，算法A1比算法B1逐步拉大差距。
所以总体上算法A1比算法B1优秀**

• 函数的渐进增长：给定两个函数f(n)和g(n)，如果存在一个整数N,使得对于所有的n>N，f(n)总是比g(n)大，那么，我们说f(n)的增长渐进快于g(n)。(N是一个起始点，从n往后逐渐增大)
• 从刚才的对比可以发现，随着n的增大，后面的+3和+1其实不影响最终的算法变化曲线的。
• 例如算符A2,B2,在图中他们压根被覆盖了。所以，我们可以忽略这些加法常数。

结论

判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高项）的阶数。