1.算法分析基本步骤

1. Observations: 观察程序运行的特点（比如执行时间等）
2. Mathematical Models： 建立一些模型
3. 使用算法理论分析

2. observations

3 SUM问题
给定N个不同的整数（N>=3），有多少种方式可以使得其中三个数字加起来为0

这个问题实际上在现实中有很多应用，例如在计算机几何学问题中有重要应用。

较好的解决算法的时间复杂度为O(N^2logN)

步骤：

1. 排序，O(logN)
2. 计算所有两两组合的值(a[i]+a[j])，O(N^2)
3. 在有序序列中二分查找-(a[i]+a[j]),O(logN)
4. 因此总的复杂度2O(logN)*O(N^2)，即O(N^2logN)

注意点：只计算a[i]<a[j]<a[k]的顺序，避免重复计算

PS: 除了3加问题，还有1加问题（N个数中找为0的数），2加问题（N个数找2个加起来为0的数）

3. 按照增长速度对算法分类

4. 算法理论分析

对二分查找的算法进行分析：

可以看到，关键是利用假设条件做推导，在推导过程中重复利用假设条件

算法分析理论中会用到的一些符号，这些符号用于区分算法运行时间

1. 大Theta: 例如theta(N^2)表示运行时间在N^2这个数量级
2. O: 例如O(N^2)表示运行时间在这个N^2数量级，并且可能更加的小，例如常数时间或者线性时间，即表示的是最坏情况（上限）
3. 欧米伽： 例如O(N^2)表示运行时间在这个N^2数量级，并且可能更加的大，即表示的是最好情况（下限）
4. 波浪号：用于近似

通过比较下限和上限的时间复杂度，可以知道是否得出了算法的最优解。在这种X- SUM问题中，下限均为N，因为至少要扫描一遍所有的数。1加问题可以得出最优解，因为其上限和下限一样均为N，而三加问题则不一定，即是N^2logN也不一定是该算法的最优解。