性能分析
例子: FFT
暴力: $N^2\ steps$
FFT: $N\log N\ steps$
例子2: 三整数问题(时间分析法)
有N个整数,多少组三整数组合的和为0?
暴力算法: $N^3$
实测运行时间
如何预测当数据大小为16000个的运行时间?
画出双对数坐标图像
得到一条直线,使用幂定律(若该直线的斜率为$b$,那么函数正比于$N^b$)
对于该图像,我们有
$\lg(T(N))=b\lg N+c\ ,where\ b=2.999\ c=-33.2103$
$T(N)=aN^b,where\ a=2^c(c\ is \ constant)$
$\lg N=\log_2N$
那么我们可知运行时间大约是$1.006 \times 10^{-10} \times N^{2.999}$
带入$N = 16000$可知需要$408.1$秒
绝大多数计算机算法的运行时间满足幂定律
将输入翻倍后计算出N和2N运行时间的比率,最后会收敛到N的指数
如何计算a
数学模型
上面提到的时间模型没办法通过基本操作直观的看出来,但是数学模型可以帮助我们直接的看出来
但是很明显这样做实在是太繁琐了,而在大部分时候我们并不需要一个精细的运行时间,仅需一个粗略的可比较的就可以了,因此我们对于这几个operation选出一个最大的或最具代表性的分析即可
在此基础之上我们将对常数做一系列的简化,例如
$\frac{1}{6}N^3 + 20N + 16 \backsim \frac{1}{6}N^3$
因为显然对于极大的N,20N+16的大小可以几乎不计入
形式化的定义$\backsim$就是
$$
\lim_{N \to \infty} \frac{f(N)}{g(N)}=1
$$
如何计算离散求和的大致时间?
把离散换成积分,然后积回去
例子:
$$
\sum^N_{i=1}i \backsim \int^N_{x=1}x\ dx \backsim \frac{1}{2}N^2
$$
幸运的是,大部分算法的增长阶数是差不多的
我们一般对于算法所需的时间常数是省略的
对于二分查找算法时间度的证明
我们认为$T(N)$是二分在$\leq N$内的数组查找所需的时间
有如下递推: $T(N) \leq T(\frac{N}{2}) +1\ (N>1),T(1)=1$
那么通过裂项求和我们有
$T(N) \leq T(\frac{N}{2})+1$
$T(N) \leq T(\frac{N}{4})+1+1$
$…$
$T(N) \leq T(\frac{N}{N}) + 1+1+…$
$T(N) \leq 1+\lg N$
算法的性能表现的计数方法
$\Theta(n)$表现的是一般情况下算法的运行情况
$\Theta(N^2)$可以表现为所需时间$\backsim qN^2$的
$O(n)$表现为在最差情况下算法的运行情况
$O(N^2)$可以表现为所需时间$\lesssim qN^2$的
$\Omega(n)$表现为在最优情况下算法的运行情况
$\Omega (N^2)$可以表现为所需时间$\gtrsim qN^2$的
内存
32位和64位的区别
支持寻址更多位的内存
指针使用更多空间