本博客采用创作共用版权协议, 要求署名、非商业用途和保持一致. 转载本博客文章必须也遵循署名-非商业用途-保持一致的创作共用协议.

#1. 算法设计基础

算法是有限条指令序列, 确定了解决某个问题的一系列运算或操作

  1. 问题建模
  2. 选择什么算法
  3. 这个算法能否使所有实例得到最优解
  4. 如果不能, 找出反例

算法时间复杂度: 针对指定基本运算, 计算算法所做运算次数

#2. 算法数学基础

$$\sum\limits_{k=1}^na_k = \frac{n(a_1 + a_n)}{2}$$

$$\sum\limits_{k=0}^naq^k = \frac{a(1 - q^{n + 1}))}{1 - q}$$

$$\sum\limits_{k=1}^n\frac{1}{k} = lnn + O(1)$$

估计序列和:

  1. 和式放大法 $ \sum\limits_{k=1}^nak <= na{max} $ , 等比数列方法法

  2. 积分法

求解递推方程:

  1. 迭代法(代入前一项的值)
  2. 差消法(利用两个方程相减, 尽可能的销项)

递归树是一个迭代计算模型, 生成过程与迭代过程一致

$$T(n) = aT(n/b) + f(n)$$

a: 规约后的子问题个数
n/b: 规约后子问题的规模
f(n): 规约过程及组合子问题的解的工作量

##主定理

用于计算算法的时间复杂度

定理: 设$a\geq1, b>1$为常数,$f(n)$为函数, $T(n)$为非负整数, 且$T(n) = aT(a/b) + f(n)$, 则

  1. 若$f(n) = O(n^{log_ba - \epsilon}), \epsilon>0$, 那么$$T(n) = \Theta(n^{log_ba})$$
  2. 若$f(n) = \Theta(n^{log_ba})$, 那么$$T(n) = \Theta(n^{log_ba}logn)$$
  3. 若$f(n) = \Omega(n^{log_ba + \epsilon}), \epsilon>0$, 且对于某个常数$c<1$和充分大的$n$有$af(b/b) \leq cf(n)$, 那么$$T(n) = \Theta(f(n))$$

#3. 分治算法

分支策略 :将原问题划分成规模较小的子问题, 递归或迭代求解子问题(独立), 将子问题的解综合得到原问题的解

  • 快速排序
  • 幂乘运算(奇数次和偶数次, 划分成规模减半子问题)
  • 矩阵乘法(矩阵分块策略)
  • 平面距离最小点对问题(平面进行划分)

分支算法时间复杂度方程:

$$ W(n) = aW(n/b) + d(n)$$

a为子问题数, n/b为子问题规模, d(n)为划分和综合的工作量
当a较大, b较小, d(n)不大时, 方程的解:
$$W(n) = \Omega(n^{log_ba}) $$

减少a是降低函数$W(n)的阶的途径$

未完待续…