week1——算法分析

声明

本文是博主在Coursera学习时所写的学习笔记，如有错误疏漏还望各位指正。

欢迎交流讨论

如果大家转载，请注明本文地址！

---

简介

1.分析算法的必要性

• 预测算法的性能
• 用于算法之间的比较
• 提供担保（当数据量较大时，对性能的保证）
• 学习理论基础
• 避免bug

---

2.如何分析算法

方法：

1. 观察特征
2. 基于观察结果假设出数学模型
3. 对假设出的模型进行预测
4. 通过进一步的观察证实假设
5. 修改模型，直至假设与观察结果一致

原则：
- 实验必须是可重复的
- 假设必须是可证伪的

---

观察

通过一个例子来介绍这部分

例子

问题：给定N个确定的数字，找出三个数字之和为0的组合的个数
例如：
输入：30，-20，-40，-10，40，0，10，5
因为符合要求的组合为4个
1. 30 -40 10
2. 30 -20 -10
3. -40 40 0
4. -10 0 10
所以输出为 4

解决算法

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;}

这是算法采用的方式暴力破解，通过三重循环遍历所有组合并检测其和是否为0

测试算法运行时间

不同输入结果的运行时间

分析

通过对数运算对结果进行缩放，$lg(T(N)) = blgN+a$
其中$T(N)$是时间关于N的函数，$T (N) = aN^b$ , $a,b$是常数

假设

讲观察结果和分析进行结合，做出假设
假设：运行时间 $T = 1.006 × 10^{-10} × N^{2.999}$s

预测

N = 8000，T = 51.0s
N = 16000, T = 408.1s

观察

加倍法预测

通过加倍法预测可以快速估算b

其中b = $log(ratio)$，可以观测出b的值趋近于3
注：此方法不可以确定加速因子

计算a：
取较大的N，进行测试得到a

影响因素

独立因素：

• 输入数据
• 算法

相关因素：
- 硬件：cpu，内存…
- 软件：编译器，解释器…
- 系统：网络，操作系统…

---

数学模型

影响一个算法运行时间的因素有很多，但归根结底还执行的指令数与执行每条指令所需要的时间。分析算法时应该分析当算法运行时执行的指令数，并当输入数据增多时，执行指令数的增长速率是怎样的。

分析指令

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$
• 小于比较：$\frac12(N+1)(N+2)$
• 等于比较：$\frac12N(N-1)$
• 数组访问：$N(N-1)$
• 增量运算：$\frac12N(N-1)$ ~ $N(N-1)$

简化

但是这种分析是很繁琐且没有意义的，下面我们对其进行简化

• 建立代价模型：使用一些基本预算作为计算运行时间的基础。在此例中我们可以使用数组访问作为这种基本操作，换言之，当数组访问次数越多时，我们就认为运行时间越长。
• Tilde notation：忽略低阶项，只保留最高项。
  
  • 当N很大时，低阶项何以忽略不计
  • 我们不考虑当N很小时的算法性能
  • ex：
    
    • $N^3 + 20N + 16$ ~$N^3$
    • $N^3 + N^2 + N/2$ ~$N^3$

经过简化以后，对上述的双重循环估算就可以表示为
$N(N-1)$ ~ $N^2$
这样就极大的提高了我们分析算法的效率

---

增长模型

常见的增长模型

$1,logN,N,NlogN,N^2,N^3,2^N$

举例：

---

算法原理

Theory of algorithms

• Best case. Lower bound on cost.
• Worst case. Upper bound on cost.
• Average case. “Expected” cost.

Commonly-used notations

• $Θ(N^2)$
  表示算法的一般成本在$N^2$左右
  例如：$10N^2,5N^2+22NlogN+3N,100N$
• $O(N^2)$
  表示算法的上界成本是$N^2$
  例如：$100N,22NlogN$
• $Ω(N^2$
  表示算法的下界成本是$N^2$
  例如$N^2+22NlogN$

---

内存

在程序运行时数据以二进制的形式存在于内存中，每个二进制位(bit)的值只能为0或1，8个二进制位称为一个字节(byte)
1GB(Gigabyte) = $2^{30}$ bytes
1MB(Megabyte) = $2^{20}$ bytes

各类数据在内存中占用的字节数

$$\begin{array}{c|lcr} type & \text{bytes}\\ \hline boolean & 1 \\byte &1 \\ char&2 \\int&4\\float&4\\long&8\\double&8 \end{array}$$
一维数组：
$$\begin{array}{c|lcr} type & \text{bytes}\\ \hline char[ ] & 2N+4 \\int[] & 4N+4 \\ double[]&8N+24\end{array}$$
二维数组：
$$\begin{array}{c|lcr} type & \text{bytes}\\ \hline char[ ][] & 2M*N \\int[] & 4M*N\\ double[]&8M*N\end{array}$$
对象：

• object overhead：16bytes
• pading：填充适量空白字节使每个对象所占的字节数为8的倍数
  举个例子：

public class MysteryBox {
                               // 16 (object overhead)private final int x0, x1, x2, x3;               // 16 (4 int)private final boolean y0, y1, y2, y3;           // 4 (4 boolean)private final long z0, z1;                      // 16 (2 long)private final double[] a = new double[72];      // 8 (reference to array)// 600 (double array of size 72)//4 (padding to round up to a multiple of 8)
}                                                      ----共664字节