算法数学基础 - 1

算法研究的主要内容


  1. 计算复杂性理论(Computational complexity theory)

    • 常见问题:

      • 货郎问题 (NP-hard 问题)

      • 0-1背包问题

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

      • 双机调度问题

    • NP-hard问题

      • 问题有数千个,大量存在于各个领域;

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

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

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

    • 程序 = 算法 + 数据结构

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

      • 算法的研究目标:

        问题 → 建模并寻找算法 (算法技术设计)

        算法 → 算法的评价 (算法分析方法)

        算法类 → 问题复杂度的估计 (问题复杂度分析)

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

    • NP完全理论

  1. 问题复杂度:

    以排序算法(插入、冒泡、快排、堆排、归并)

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

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

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

    • 其他问题的计算复杂度

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

  2. 算法设计与分析(调度问题、背包问题和投资问题)

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

    • 设计算法:采用什么算法设计技术?

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

    • 分析算法——效率

算法的相关概念

  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)W(n)

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

    SS是规模为nn的实例集,实例ISI \in S的概率为PIP_I,算法对实例II执行的基本运算次数为tIt_I

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

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

    • 大O符号

      定义:设ffgg是定义域为自然数集NN上的函数。若存在正数ccn0n_0,使得对一切nn0n \ge n_00f(n)cg(n)0 \le f(n) \le c g(n) 成立,则称f(n)f(n)的渐近界上界是g(n)g(n),记作f(n)=O(g(n))f(n)=O(g(n))

      举例:f(n)=n2+nf(n)=n^2+n,则 f(n)=O(n2)f(n)=O(n^2),取c=2,n0=1c=2,n_0=1即可;f(n)=O(n3)f(n)=O(n^3),取c=1,n0=2c=1,n_0=2即可。

      注意:

      • f(n)=O(g(n))f(n)=O(g(n))f(n)f(n)的阶不高于g(n)g(n)的阶;

      • 可能存在多个正数cc,只要指出一个即可;

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

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

    • 大Ω符号

      定义:设ffgg是定义域为自然数集NN上的函数。若存在正数ccn0n_0,使得对一切nn0n \ge n_00cg(n)f(n)0 \le cg(n) \le f(n) 成立,则称f(n)f(n)的渐近的下界是g(n)g(n),记作 f(n)=Ω(g(n))f(n) = \Omega(g(n))

      举例:f(n)=n2+nf(n)=n^2+n,则f(n)=Ω(n2)f(n)=\Omega(n^2),取c=1,n0=1c=1,n_0=1即可;f(n)=Ω(100n)f(n)=\Omega(100n),取c=1/100,n0=1c=1/100,n_0=1即可。

      注意:

      • f(n)=Ω(g(n))f(n)=\Omega(g(n))f(n)f(n)的阶不低于g(n)g(n)的阶(下界);

      • 可能存在多个正数cc,指出一个即可;

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

    • 小o符号

      定义:设ffgg是定义域为自然数集NN上的函数。若对于任意正数cc都存在n0n_0,使得对一切nn0n \ge n_00f(n)<cg(n)0 \le f(n) < cg(n)成立,则记作 f(n)=o(g(n))f(n)=o(g(n))

      举例: f(n)=n2+nf(n)=n^2+n,则f(n)=o(n3)f(n)=o(n^3),

      c1c\ge1显然成立,因为n2+n<cn3,(n0=2)n^2+n<cn^3,(n_0=2);

      1>c>01>c>0,取n0>2/cn_0>\ulcorner2/c\urcorner即可。因为cncn02,(nn0)cn\ge cn_0 \ge 2, (n\ge n_0)n2+n<2n2<cn3n^2+n<2n^2<cn^3成立。

      注意:

      • f(n)=o(g(n))f(n)=o(g(n))f(n)f(n)的阶低于g(n)g(n)的阶;

      • 对于不同的正数ccn0n_0不一样,cc越小n0n_0越大;

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

    • 小ω符号

      定义:设ffgg是定义域为自然数集NN上的函数。若对于任意正数cc都存在n0n_0,使得对一切nn0n \ge n_00cg(n)<f(n)0 \le cg(n) < f(n) 成立,则记作 f(n)=ω(g(n))f(n) = \omega(g(n))

      举例:f(n)=n2+nf(n)=n^2+n,则f(n)=ω(n)f(n)=\omega(n)。不能写f(n)=ω(n2)f(n)=\omega(n^2),因为取c=2c=2,不存在n0n_0使得对一切nn0n\ge n_0有下式成立 cn2=2n2<n2+ncn^2=2n^2<n^2+n

      注意:

      • f(n)=ω(g(n))f(n)=\omega (g(n))f(n)f(n)的阶高于g(n)g(n)的阶(下界);

      • 对于不同的正数ccn0n_0不等,cc越大n0n_0越大;

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

    • θ符号

      定义:若f(n)=O(g(n))f(n)=O(g(n))f(n)=Ω(g(n))f(n)=\Omega(g(n)),则记作f(n)=Θ(g(n))f(n)=\Theta(g(n))

      举例: f(n)=n2+n,g(n)=100n2f(n)=n^2+n, g(n)=100n^2,那么有f(n)=Θ(g(n))f(n)=\Theta(g(n))

      注意:

      • f(n)f(n)的阶与g(n)g(n)的阶相等;

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

  7. Big-O标记

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

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

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

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

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

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

作者

Hu

发布于

2020-05-13

更新于

2020-05-13

许可协议

评论