算法分析
算法简介
简单来说，所谓算法就是定义良好的计算过程，它取一个或一组值作为输入，并产生出一个或一组值作为输出。亦即，算法就是一系列的计算步骤，用来将输入数据转换成输出结果。
算法分析
算法分析是关于计算机程序性能与资源利用的研究。
计算时间是一种有限的资源，存储空间也是一种有限的资源。
算法尤其关注性能, 这是门关于性能的学问。
循环不变化
循环不变化主要用来帮助我们理解算法的正确性。对于循环不变式，必须证明他的三个性质：
- 初始化: 它在循环的第一轮迭代开始之前，应该是正确的。
- 保持: 如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确。
- 终止:当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。
最坏情况和平均情况分析
一般考察算法的最坏情况运行时间。
渐近分析
淅近分析的基本思路是忽略掉那些依赖于机器的常量, 以及，不去检查实际的运行时间，而是关注运行时间的增长。
当n->∞,有 ( \Theta(n^3) < \Theta(n^2) < \Theta(n) < \Theta(lgn) < \Theta(1))
此处<表示消耗时间少，效率更高。
简化分析方法
从极限角度看，我们只关心算法运行时间如何随着输入规模的无限增长而增长。
渐近确界
( \Theta(g(n)) = {f(n): 存在正常数c_1,c_2和n_0, 使对所有的n \geq n_0, 有0 \leq c_1g(n) \leq f(n) \leq c_2g(n) } )
(\Theta(g(n))是一个集合，可以写成f(n) in \Theta(g(n)), 表示f(n)是\Theta(g(n))的元素，不过，通常写成f(n) = \Theta(g(n)) ) 我们说g(n)是f(n)的一个渐近边界。
渐近上界
( O(g(n)) = {f(n): 存在正常数c和n_0, 使对所有的n \geq n_0, 有0 \leq f(n) \leq cg(n) } )
渐近下界
( \Omega(g(n)) = {f(n): 存在正常数c和n_0, 使对所有的n \geq n_0, 有0 \leq cg(n) \leq f(n) } )
o记号
( o(g(n)) = {f(n): 对任意正常数c, 存在n_0 > 0, 使对所有的n \geq n_0, 有0 \leq f(n) \leq cg(n) } )
从直觉上看，在o表示中当n趋于无穷时，函数f(n)相对于g(n)来说不重要了，即
[\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = 0]
(\omega记号)
( \omega(g(n)) = {f(n): 对任意正常数c, 存在n_0 > 0, 使对所有的n \geq n_0, 有0 \leq cg(n) \leq f(n) } )
从直觉上看，在o表示中当n趋于无穷时，函数f(n)相对于g(n)来说变得任意大了，即
[\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = \infty]
定理
对任意两个函数f(n)和g(n), \(f(n) = \Theta(g(n))当且仅当f(n)=O(g(n)) 和 f(n) = \Omega(g(n))。\)
实际应用中，一般是用渐近上界和渐近下界证明了渐近确界。
等式和不等式中的渐近记号
- 只出现在等式(不等式)的右边： 表示集合的成员关系。如\(n=O(n^2)\)
- 一般来说，当出现在某个公式中时, 我们将其解释为一个不在乎其名称的匿名函数。如\(2n^2 + 3n + 1 = 2n^2 + \Theta(n) 即表示2n^2 + 3n + 1 = 2n^2 + f(n), 其中f(n)是某个属于\Theta(n)的函数。\)
- 有时，出现在等式的左边，例如\(2n^2 + \Theta(n) = \Theta(n^2)\) 这时，我们使用以下规则来解释这种等式：无论等号左边的匿名函数如何选择， 总有办法选取选号右边的匿名函数使等式成立。
递归式的解法
代换法
步骤：
- 猜测解的形式。
- 用数学归纳法找出使解真正有效的常数。
适用情形：
只能用于解的形式很容易猜的情形。
递归树方法
用代换法不好猜，我们可以用递归树方法获得一个猜想，然后用代换法加以验证。
当用递归式表示分治算法的运行时间时，递归树的方法尤其有用。
主方法
主方法给出求解如下形式的递归式的”食谱”方法：
[ T(n) = aT(n/b) + fn(n)]
其中(a \geq 1 和 b > 1 是常数, f(n)是一个渐近正的函数)。
有三种情况：
- \(若对于某常数\varepsilon > 0, 有f(n) = O(n^{log_b{a-\varepsilon}}), 则T(n)＝\Theta(n^{log_ba});\)
- \(若f(n)=\Theta(n^{log_ba}), 则T(n) = \Theta(n^{log_ba}lgn)\);
- \(若对某常数\varepsilon>0, 有f(n)＝\Omega(n^{log_b{a+\varepsilon}}), 且对常数c<1与所有足够大的n,\) \(有af(n/b) \leq cf(n), 则T(n)=\Theta(f(n)) \);
需要注意三种情况并没有覆盖所有可能的f(n)。
算法设计
增量方法
插入排序有的就是增量方法。
分治法
分治模式在每一层递归上都有三个步骤：
- 分解：将原问题分解成一系统子问题。
- 解决：递归地解决各子问题。若子问题足够小，则直接求解。
- 合并：将子问题的结果合并成原问题的解。