算法分析

• 算法分析
• 算法简介
• 算法分析
  • 循环不变化
  • 最坏情况和平均情况分析
  • 渐近分析
    • 简化分析方法
    • 等式和不等式中的渐近记号
  • 递归式的解法
    • 代换法
    • 递归树方法
    • 主方法
• 算法设计
  • 增量方法
  • 分治法

算法简介

简单来说，所谓算法就是定义良好的计算过程，它取一个或一组值作为输入，并产生出一个或一组值作为输出。亦即，算法就是一系列的计算步骤，用来将输入数据转换成输出结果。

算法分析

算法分析是关于计算机程序性能与资源利用的研究。
计算时间是一种有限的资源，存储空间也是一种有限的资源。
算法尤其关注性能, 这是门关于性能的学问。

循环不变化

循环不变化主要用来帮助我们理解算法的正确性。对于循环不变式，必须证明他的三个性质：

• 初始化: 它在循环的第一轮迭代开始之前，应该是正确的。
• 保持: 如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确。
• 终止:当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。

最坏情况和平均情况分析

一般考察算法的最坏情况运行时间。

渐近分析

淅近分析的基本思路是忽略掉那些依赖于机器的常量, 以及，不去检查实际的运行时间，而是关注运行时间的增长。

当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)\) 这时，我们使用以下规则来解释这种等式：无论等号左边的匿名函数如何选择， 总有办法选取选号右边的匿名函数使等式成立。

递归式的解法

代换法

步骤：

1. 猜测解的形式。
2. 用数学归纳法找出使解真正有效的常数。

适用情形：
只能用于解的形式很容易猜的情形。

递归树方法

用代换法不好猜，我们可以用递归树方法获得一个猜想，然后用代换法加以验证。

当用递归式表示分治算法的运行时间时，递归树的方法尤其有用。

主方法

主方法给出求解如下形式的递归式的”食谱”方法：

[ T(n) = aT(n/b) + fn(n)]
其中(a \geq 1 和 b > 1 是常数, f(n)是一个渐近正的函数)。

有三种情况：

1. \(若对于某常数\varepsilon > 0, 有f(n) = O(n^{log_b{a-\varepsilon}}), 则T(n)＝\Theta(n^{log_ba});\)
2. \(若f(n)=\Theta(n^{log_ba}), 则T(n) = \Theta(n^{log_ba}lgn)\);
3. \(若对某常数\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)。

算法设计

增量方法

插入排序有的就是增量方法。

分治法

分治模式在每一层递归上都有三个步骤：

• 分解：将原问题分解成一系统子问题。
• 解决：递归地解决各子问题。若子问题足够小，则直接求解。
• 合并：将子问题的结果合并成原问题的解。