算法分析

  • 简介
  • 观察
  • 数学模型
  • 增长顺序分类
  • 算法理论
  • 内存

简介

为什么要做算法分析：

  • 预测性能
  • 比对算法
  • 提供保证
  • 避免性能错误
    最主要是避免性能bug

成功算法的例子：FFT
快速傅里叶变换（这好像高斯以前手稿提过，认为含金量，故未发表，大物课上有提到）

暴力算法：n**2
FFT：n log n

当我们做算法分析时，应该考虑程序是否能适应大规模数据。性能是否足够（速度、内存）

观察

3-sum:给定n个整型数据，有多少组（每组三个元素）元素和为0

javac测算运行时间的函数：

1
2
3
4
5
6
7
8
public static void main(String[] args)
{
 int[] a = In.readInts(args[0]);
 Stopwatch stopwatch = new Stopwatch();
 StdOut.println(ThreeSum.count(a));
 double time = stopwatch.elapsedTime();
}

我们发现对于不同的数据，程序运行时间大致为aN*b ,b=lg ratio

其中b的影响因子有：

  • 算法
  • 输入数据

而a的影响因子有：

  • 硬件：CPU，内存，缓存
  • 软件:编译器，解释器，垃圾回收器
  • 系统：操作系统、网路、其他app
  • 以及算法和输入数据

这很精确得到测量，但对比其他科学更便宜更方便

数学模型

运行时间：所有操作的成本*频率之和

  • 需要分析程序去决定操作集
  • 成本取决于机器、编译器
  • 频率取决于算法和输入数据

不同的operation的运行的h时间是不同的（加减乘除、浮点数整数都不一样）

字符串的连接通常耗费很多时间，切勿滥用

“ It is convenient to have a measure of the amount of work involved
in a computing process, even though it be a very crude one. We may
count up the number of times that various elementary operations are
applied in the whole process and then given them various weights.
We might, for instance, count the number of additions, subtractions,
multiplications, divisions, recording of numbers, and extractions
of figures from tables. In the case of computing with matrices most
of the work consists of multiplications and writing down numbers,
and we shall therefore only attempt to count the number of
multiplications and recordings. “