算法数学基础 - 1

算法研究的主要内容

---

1. 计算复杂性理论（Computational complexity theory）

   • 常见问题：

     • 货郎问题 （NP-hard 问题）

     • 0-1背包问题

       问题的解为0-1向量 $<X_1,X_2,...,Xn_>$

     • 双机调度问题

   • NP-hard问题

     • 问题有数千个，大量存在于各个领域；

     • 至今未找到有效算法：现有算法的运行时间是输入规模的指数或更高阶函数；、

     • 至今没有人能够证明对于这类问题存在多项式时间算法；

     • 是否存在多项式时间算法等价于存在有效计算的边界

   • 程序 = 算法 + 数据结构

     • 好的算法： 提高求解问题的效率；节省存储空间

     • 算法的研究目标：

       问题 → 建模并寻找算法 （算法技术设计）

       算法 → 算法的评价 （算法分析方法）

       算法类 → 问题复杂度的估计 （问题复杂度分析）

       问题类 → 能够求解的边界 （计算复杂性理论）

   • NP完全理论

2. 问题复杂度：

   以排序算法（插入、冒泡、快排、堆排、归并）

   • 哪个个排序算法效率高？

   • 是否可以找到更好的排序算法？

   • 排序问题的计算难度如何？

   • 其他问题的计算复杂度

   • 问题计算复杂度估计方法

3. 算法设计与分析（调度问题、背包问题和投资问题）

   • 问题建模？对输入参数和解给出形式化或半形式化的描述。

   • 设计算法：采用什么算法设计技术？

   • 正确性：这个方法是否对所有实例都得到最优解？如何证明？如果不是，能否找到反例？

   • 分析算法——效率

算法的相关概念

1. 问题及实例

   • 问题：需要回答的一般性提问，通常含有若干参数

   • 问题描述：

     • 定义问题参数（集合、变量、函数、序列等）；

     • 说明每个参数的取值范围及参数间的关系；

     • 定义问题的解；

     • 说明解满足的条件（优化目标或约束条件）

   • 问题实例

     参数的每一组赋值可以得到问题的实例

2. 什么是算法？

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

   算法A解问题P：

   • 把问题P的任何实例作为算法A的输入

   • 每步计算都是确定性的

   • 能够在有限步停机

   • 输出该实例的正确的解

3. 算法的表示 （伪代码）

   • 赋值语句： ←

   • 分支语句：if ... then ... [else...]

   • 循环语句：while, for, repeat until

   • 转向语句：goto

   • 输出语句：return

   • 调用：直接写过程的名字

   • 注释：//..

4. 算法时间复杂度定义？

   • 算法时间复杂度：针对指定的基本运算，计数算法所做的运算次数。

   • 基本运算：比较、加法、乘法、置指针、交换……

     • 排序：元素之间的比较

     • 检索：被检索元素与数组元素的比较

     • 整数乘法：每位数字相乘（位乘）1次m位和n位整数相乘要做mn次位乘

     • 矩阵相乘：每对元素乘1次 i×j 矩阵与j×k矩阵相乘要做ijk次乘法

     • 图的遍历：置指针

     • ……

   • 输入规模：输入串编码长度

     通常用下述参数度量：数组元素多少，调度问题的任务个数，图的顶点数与边数等。

     • 排序：数组元素个数n

     • 检索：被检索数组的元素个数n

     • 整数乘法：两个整数的位数 m，n

     • 矩阵相乘：矩阵的行列数i,j,k

     • 图的遍历：图的顶点数n，边数m

     • ……

   • 算法基本运算次数可表示为输入规模的函数

   • 给定问题和基本运算决定了一个算法类。

5. 时间复杂度函数的表示：函数渐近的界

   对于相同输入规模的不同实例，算法的基本运算次数也不一样，可以定义为两种时间复杂度。

   • 最坏情况下的时间复杂度 $W(n)$

   • 平均情况下的时间复杂度$A(n)$

   设$S$是规模为$n$的实例集，实例$I \in S$的概率为$P_I$，算法对实例$I$执行的基本运算次数为$t_I$。

   $A(n) = \sum_{I \in S} P_It_I$

6. 有关函数渐近的界的描述

   • 大O符号

     定义：设$f$和$g$是定义域为自然数集$N$上的函数。若存在正数$c$和$n_0$，使得对一切$n \ge n_0$有 $0 \le f(n) \le c g(n)$ 成立，则称$f(n)$的渐近界上界是$g(n)$，记作$f(n)=O(g(n))$。

     举例： 设$f(n)=n^2+n$，则 $f(n)=O(n^2)$，取$c=2,n_0=1$即可；$f(n)=O(n^3)$，取$c=1,n_0=2$即可。

     注意：

     • $f(n)=O(g(n))$，$f(n)$的阶不高于$g(n)$的阶；

     • 可能存在多个正数$c$，只要指出一个即可；

     • 对前面有限个值可以不满足不等式；

     • 对于常函数可以写作$O(1)$。

   • 大Ω符号

     定义：设$f$和$g$是定义域为自然数集$N$上的函数。若存在正数$c$和$n_0$，使得对一切$n \ge n_0$ 有 $0 \le cg(n) \le f(n)$ 成立，则称$f(n)$的渐近的下界是$g(n)$，记作 $f(n) = \Omega(g(n))$。

     举例： 设$f(n)=n^2+n$，则$f(n)=\Omega(n^2)$，取$c=1,n_0=1$即可；$f(n)=\Omega(100n)$，取$c=1/100,n_0=1$即可。

     注意：

     • $f(n)=\Omega(g(n))$，$f(n)$的阶不低于$g(n)$的阶（下界）；

     • 可能存在多个正数$c$，指出一个即可；

     • 对前面有限个$n$值可以不满足上述不等式。

   • 小o符号

     定义：设$f$和$g$是定义域为自然数集$N$上的函数。若对于任意正数$c$都存在$n_0$，使得对一切$n \ge n_0$ 有$0 \le f(n) < cg(n)$成立，则记作 $f(n)=o(g(n))$。

     举例： $f(n)=n^2+n$，则$f(n)=o(n^3)$,

     当 $c\ge1$显然成立，因为$n^2+n<cn^3,(n_0=2)$;

     当$1>c>0$，取$n_0>\ulcorner2/c\urcorner$即可。因为$cn\ge cn_0 \ge 2, (n\ge n_0)$， $n^2+n<2n^2<cn^3$成立。

     注意：

     • $f(n)=o(g(n))$，$f(n)$的阶低于$g(n)$的阶；

     • 对于不同的正数$c$，$n_0$不一样，$c$越小$n_0$越大；

     • 对前面有限个$n$值可以不满足不等式。

   • 小ω符号

     定义：设$f$和$g$是定义域为自然数集$N$上的函数。若对于任意正数$c$都存在$n_0$，使得对一切$n \ge n_0$有 $0 \le cg(n) < f(n)$ 成立，则记作 $f(n) = \omega(g(n))$。

     举例： 设$f(n)=n^2+n$，则$f(n)=\omega(n)$。不能写$f(n)=\omega(n^2)$，因为取$c=2$，不存在$n_0$使得对一切$n\ge n_0$有下式成立 $cn^2=2n^2<n^2+n$。

     注意：

     • $f(n)=\omega (g(n))$，$f(n)$的阶高于$g(n)$的阶（下界)；

     • 对于不同的正数$c$，$n_0$不等，$c$越大$n_0$越大；

     • 对前面有限个$n$值可以不满足不等式。

   • θ符号

     定义：若$f(n)=O(g(n))$且$f(n)=\Omega(g(n))$，则记作$f(n)=\Theta(g(n))$。

     举例： $f(n)=n^2+n, g(n)=100n^2$，那么有$f(n)=\Theta(g(n))$。

     注意：

     • $f(n)$的阶与$g(n)$的阶相等；

     • 对前面有限个$n$值可以不满足条件。

7. Big-O标记

   O(1) 常量，运行时间和元素个数无关；

   O(log(n)) 对数，运行时间随元素个数的增加呈对数增长；

   O(n) 线性，运行时间随元素个数的增加呈线性增长；

   O(nlog(n)) n-log-n，运行时间随元素个数的增加呈“线性与对数的乘积”的增长；

   O(n^2) 二次方，运行时间随元素个数的增加呈平方增长。

   Big-O标记隐藏（忽略）了指数较小的因子。