算法分析
这一节主要讲述算法复杂度的分析，本文进行了一些精简
科学的分析方法（个人认为这里有些类似机器学习的分析法）：
- 观察现实中事物
- 根据观察结果提出一些假说的模型
- 根据之前提出的假说提出一些预测
- 验证这些预测是否与事实相符
- 重复修正模型只到预测与事实相符合
原则：
- 实验必须是可重复的
- 假说必须是可以进行验证的
看一个例子
3-sum：给出一组数字，有哪些三个一组的数字和是一个给定的值？
未进行复杂度优化时的代码实现：
public class ThreeSum
{
public static int count(int[] a)
{
int N = a.length;
int count = 0;
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
for (int k = j+1; k < N; k++)
if (a[i] + a[j] + a[k] == 0) //三重循环
count++;
return count;
}
public static void main(String[] args)
{
int[] a = In.readInts(args[0]);
StdOut.println(count(a));
}
}
直观图：
屏幕快照 2018-07-30 下午4.46.13.png
取对数后的图
屏幕快照 2018-07-30 下午4.48.23.png
我们有以下公式：
lg(T (N)) = blgN + c
b = 2.999
c = -33.2103
T (N) = 2cNb
通过该公式可以通过已知的算法消耗时间推送出斜率，然后推算出当N较大时需要的时间。
数学分析
例子：当输入参数等于N时的数组访问次数
int count = 0;
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
if (a[i] + a[j] == 0)
count++;
| 操作 | 频率 |
|---|---|
| 变量声明 | N + 2 |
| 赋值操作 | N + 2 |
| 小于比较 | ½ (N + 1) (N + 2) |
| 等于比较 | ½ N (N − 1) |
| 数组访问 | N (N − 1) |
| 自增 | ½ N (N − 1) 至 N (N − 1) |
简化算法复杂度的衡量指标
忽略低等级指数项 如：
⅙ N 3 - ½ N 2 + ⅓ N 直接使用： ⅙ N 3
增长级别分类：
常用的算法复杂度增长函数有：
1, log N, N, N log N, N 2, N 3,2N
屏幕快照 2018-07-30 下午5.21.37.png
下面的表格展示了1970年以来我们能处理的不同算法复杂度的问题规模
| 算法复杂度 | 1970s | 1980s | 1990s | 2000s |
|---|---|---|---|---|
| 1 | ∞ | ∞ | ∞ | ∞ |
| logN | ∞ | ∞ | ∞ | ∞ |
| N | 百万 | 千万 | 亿 | 十亿 |
| NlogN | 几千 | 百万 | 百万 | 数百万 |
| N2 | 百 | 千 | 千 | 万 |
| N3 | 百 | 百 | 千 | 千 |
| 2N | 20 | 20s | 20s | 30 |
例子
二分查找：
public static int binarySearch(int[] a, int key)
{
int lo = 0, hi = a.length-1;
while (lo <= hi)
{
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
二分查找的算法复杂度为lgN，下面我们尝试使用这个算法去精简3-sum算法。
- 首先对数据进行排序，在已知的算法中可以做到复杂度为NlogN（归并排序或者堆排序）
- 而后对于每一组a[i] a[j]查找-(a[i]+a[j]).对于(a[i]+a[j])转换为2sum问题，在数组中二分查找a[i].
