1.算法分析基本步骤
- Observations: 观察程序运行的特点(比如执行时间等)
- Mathematical Models: 建立一些模型
- 使用算法理论分析
2. observations
3 SUM问题
给定N个不同的整数(N>=3),有多少种方式可以使得其中三个数字加起来为0
这个问题实际上在现实中有很多应用,例如在计算机几何学问题中有重要应用。
较好的解决算法的时间复杂度为O(N^2logN)
步骤:
- 排序,O(logN)
- 计算所有两两组合的值(a[i]+a[j]),O(N^2)
- 在有序序列中二分查找-(a[i]+a[j]),O(logN)
- 因此总的复杂度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. 算法理论分析
对二分查找的算法进行分析:
可以看到,关键是利用假设条件做推导,在推导过程中重复利用假设条件
算法分析理论中会用到的一些符号,这些符号用于区分算法运行时间
- 大Theta: 例如theta(N^2)表示运行时间在N^2这个数量级
- O: 例如O(N^2)表示运行时间在这个N^2数量级,并且可能更加的小,例如常数时间或者线性时间,即表示的是最坏情况(上限)
- 欧米伽: 例如O(N^2)表示运行时间在这个N^2数量级,并且可能更加的大,即表示的是最好情况(下限)
- 波浪号:用于近似
通过比较下限和上限的时间复杂度,可以知道是否得出了算法的最优解。在这种X- SUM问题中,下限均为N,因为至少要扫描一遍所有的数。1加问题可以得出最优解,因为其上限和下限一样均为N,而三加问题则不一定,即是N^2logN也不一定是该算法的最优解。