开发高效算法

1. 引言

算法设计是为了解决某个问题开发一个数学流程。算法分析是预测一个算法的性能。

2. 使用大O符号来衡量算法效率

大O符号标记可以基于输入的大小得到一种衡量算法时间复杂度的函数。可以忽略函数中的倍乘常量和非主导项。其本质是比较算法之间的增长率。对于一个线性查找的算法，其时间复杂度表示方法为O(n)，读作“n阶”。
- 最佳情况输入：导致最短执行时间的输入
- 最差情况输入：导致最长执行时间的输入，可以确定算法不会比最差情况还慢

分析通常针对最坏情况进行。大O符号允许忽略非主导部分（例如，表达式n-1中的-1），并强调重要部分（例如，表达式n-1中的n），因此，该算法的复杂度为O(n)。如果执行时间与输入规模无关就称该算法耗费了常量时间，用符号O(1)表示。

1 + 2 + 3 + . . . + (n - 2) + (n - 1) = \frac{n (n - 1)}{2} = O (n^{2})

a^{0} + a^{1} + a^{2} + . . . + a^{n} = \frac{a^{n + 1} - 1}{a - 1} = O (a^{n})

备注：时间复杂度是使用大O标记对运行时间进行测量。类似的，也可以使用大O标记对空间复杂度进行测量。

3. 分析算法的时间复杂度

3.1 二分查找算法

每次迭代包含固定次数的操作，次数由c来表示，不失一般性，假定n是2的幂,采用递推公式求解。

T (n) = T (\frac{n}{2}) + c = T (\frac{n}{2^{2}}) + 2 + 2 = T (\frac{n}{2^{k}}) + k c

当递推到最后一个元素时，前部分为T(1)

k = l o g n

T (n) = T (1) + c \log n = O (\log n)

3.2 常用的递推关系

递推关系对于分析算法时间复杂度非常有用，常用的递推关系如下表格,其时间复杂度的递推方法与3.1方法相同

地推关系	结果	示例
$T (n) = T (n / 2) + O (1)$	$T (n) = O (\log n)$	二分查找，欧几里得求解最大公约数
$T (n) = T (n - 1) + O (1)$	$T (n) = O (n)$	线性查找
$T (n) = 2 T (n / 2) + O (1)$	$T (n) = O (n)$
$T (n) = 2 T (n / 2) + O (n)$	$T (n) = O (n \log n)$	归并排序
$T (n) = T (n - 1) + O (n)$	$T (n) = O (n^{2})$	选择排序
$T (n) = 2 T (n - 1) + O (1)$	$T (n) = O (2^{n})$	汉诺塔
$T (n) = T (n - 1) + T (n - 2) + O (1)$	$T (n) = O (2^{n})$	递归的斐波那契算法

3.3 比较常用的增长函数

开发高效算法

函数增长趋势

4. 总结

大O标记是分析算法性能的理论方法。他估计算法的执行时间随着输入规模的增加会有多快的增长。因此，可以通过检查两个算法的增长率来比较他们。
最佳情况和最差清空都不具有代表性，但是最差情况分析非常有用。你可以确保算法永远不会比最差情况还慢

参考资料：《Java语言程序设计（进阶篇）》