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也不一定是该算法的最优解。