Algorithm Design and Analysis 计算机科学与技术专业课程 Algorithm Design and Analysis 算法设计与分析 宋传鸣 chmsong@lnnu.edu.cn 辽宁师范大学计算机与信息技术学院

渐近复杂性(Asymptotic Complexity) 定义:对于T(n),如果存在 ,使得当 时有 则称 是T(n)当 时的渐近性态, 也称算法的渐近复杂性 直观上,T(n)是 略去低阶项后所留下的主项 用法 当问题规模充分大时,只需考察算法再渐近性态下的复杂性 它是T(n)的一种简化,目的在于比较两个具有不同阶复杂性的算法的效率 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近分析的记号 渐近上界记号O: 如果存在正常数c 和 使得当 时,有 ,则称函数f(n)当n充分大时有上界,且g(n)是它的一个上界,记为 非紧上界记号o:如果对于 ,都存在 使 得当 时,有 ,则称函数f(n)当n充 分大时的阶比g(n)低,记为 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近分析的记号 非紧下界记号ω:如果对于 ,都存在 使 得当 时,有 ,则称函数f(n)当n充分 大时的阶比g(n)高,记为 四种记号含义的比较 O与o类似,主要区别在于:满足o的函数集合的势要大于满足O的函数集合的势 同理,Ω与ω类似 在评价算法的复杂性时,上界的阶越低,下界的阶越高,则评估越精确,结果越有价值 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近分析的记号 紧渐近界记号θ:如果存在正常数c1,c2和 使 得当 时,有 ,则称函数f (n)当n充分大时与g(n)同阶,记为 定理: 当且仅当 并且 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近分析记号的若干性质 传递性 并且 ,则 自反性 对称性 当且仅当 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近分析记号的若干性质 转置对称性 渐近分析记号的算术运算 渐近分析的作用 当且仅当 如果 ,则 ,其中c为一个正常数 如果 ,则 ,其中c为一个正常数 渐近分析的作用 考察解决同一问题的不同算法的复杂性界限 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近复杂性分析中的常用函数 取整函数 取整函数的性质 :不大于x的最大整数 :不小于x的最小整数 对于n≧0, 有 渐近复杂性 渐近符号性质 基本数据结构

渐近复杂性分析中的常用函数 多项式函数 指数函数 定义: 若对于某个常数k,有 ,则称其有多项式界 对于 , 且 ,有 ,则 渐近复杂性 对于 , 且 ,有 ,则 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近复杂性分析中的常用函数 指数函数 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近复杂性分析中的常用函数 对数函数 定义: 若对于某个常数k,有 ,则称其多项式对数有界(Polylogarithmically bounded) 对于 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近复杂性分析中的常用函数 阶乘函数 定义: 斯特林(Stirling)近似公式 由此可知 渐近复杂性 渐近符号性质 常用函数 基本数据结构

不同渐近函数之间的关系 小规模数据 渐近复杂性 渐近符号性质 常用函数 基本数据结构

不同渐近函数之间的关系 中等规模数据 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近复杂性分析中的常见公式 二项式系数 设n为正整数, 则有 令x=1,有 令x=－1,有 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近复杂性分析中的常见公式 鸽巢原理 和式 如果把n个球分别放在m个盒子中,那么 存在一个盒子必定至少装 个球 存在一个盒子必定最多装 个球 存在一个盒子必定至少装 个球 存在一个盒子必定最多装 个球 和式 算术级数: 平方和: 几何级数: 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近复杂性分析中的常见公式 和式 几何级数: 对几何级数两边求导,得到 当c=2时,有 当c=1/2时,有 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近复杂性分析中的常见公式 求和的积分近似 如果f(x)是单调递减的连续函数,则 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近复杂性分析中的常见公式 求和的积分近似 如果f(x)是单调递增的连续函数,则 示例:求和式 和调和级数 的上下界 渐近复杂性 示例:求和式 和调和级数 的上下界 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近复杂性分析举例 求和 第4步的执行次数为 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近复杂性分析举例 求和 第5步的执行次数为 渐近复杂性 渐近符号性质 常用函数 基本数据结构

渐近复杂性分析中的常用函数 摘自http://bbs.sciencenet.cn/home.php?mod=spac e&uid=324529&do=blog&id=386663 渐近复杂性 渐近符号性质 常用函数 基本数据结构

链表(List) 由有限的元素或结点序列组成,结点包含数据域和 到另一个结点的链域 单链表 循环链表 双向链表 循环双向链表 堆栈:只允许在一端进行插入和删除运算的链表 队列:只允许在一端进行插入运算,而在另一端进行删除运算 渐近复杂性 渐近符号性质 常用函数 基本数据结构

树(Tree) 树是n(n≥0)个结点的有限集T,T为空时称为空树, 否则它满足如下两个条件: 有且仅有一个特定的称为根(Root)的结点 其余的结点可分为m(m≥0)个互不相交的子集,其中每个子集本身又是一棵树,并称其为根的子树 渐近复杂性 渐近符号性质 常用函数 基本数据结构

树(Tree) 基本概念 结点的度:树中的一个结点拥有的子树个数称为该结点的度.一棵树的度是指该树中结点的最大度数 孩子和双亲:树中某个结点的子树之根称为该结点的孩子(Child)或儿子,相应地,该结点称为孩子的双亲(Parents)或父亲.同一个双亲的孩子称为兄弟 路径:若树中存在一个结点序列k1,k2,…,kj,使得ki是ki+1的双亲(1≤i<j),则称该结点序列是从kl到kj的一条路径(Path)或道路 路径的长度:路径所经过的边(即连接两个结点的线段)的数目,等于j－1 祖先和子孙:若树中结点k到ks存在一条路径,则称k是ks的祖先(Ancestor),ks是k的子孙(Descendant) 结点的层数:根的层数为1,其余结点的层数等于其双亲结点的层数加1 树的高度或深度:树中结点的最大层数 渐近复杂性 渐近符号性质 常用函数 基本数据结构

树(Tree) 二叉树(Binary Tree) 二叉树是n(n≥0)个结点的有限集,它或者是空集,或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成 性质1:二叉树第i层上的结点数目最多为2i－1(i≥1) 性质2:深度为k的二叉树至多有2k－1个结点(k≥1) 性质3:在任意一棵二叉树中,若叶结点的个数为n0,度为2的结点数为n2,则n0=n2+1 性质4:在完全二叉树中,叶子数等于内部顶点数加1 性质5:具有n个结点的完全二叉树的深度为 性质6:任何有n个顶点的二叉树的高度最大是n,最小是 渐近复杂性 渐近符号性质 常用函数 基本数据结构

树(Tree) 二叉树的遍历 前序:访问结点的操作发生在遍历其左右子树之前 中序:访问结点的操作发生在遍历其左右子树之间 后序:访问结点的操作发生在遍历其左右子树之后 渐近复杂性 渐近符号性质 常用函数 基本数据结构

树(Tree) 二叉搜索树 所有存储在顶点v的左子树中的元素都小于存储在v中的元素,所有存储在顶点v的右子树中的元素都大于存储在v中的元素 用二叉搜索树表示一个集合并不是唯一的 渐近复杂性 渐近符号性质 常用函数 基本数据结构 4 6 8 9 1 3 6 3 8 1 4 9

图(Graph) 图G由一个顶点集合V和一个边集合E组成 有向图和无向图 图的表示:邻接矩阵或邻接表 渐近复杂性 渐近符号性质 常用函数 基本数据结构

图(Graph) 图的遍历 深度优先遍历:尽可能先对纵深方向进行搜索 广度优先遍历:尽可能先对横向进行搜索 渐近复杂性 渐近符号性质 常用函数 基本数据结构

堆(Heap) 一个堆是一个几乎完全的二叉树,它的每个结点都 满足:如果v和p(v)分别是结点和它的父结点,那么 存储在p(v)中的数据项的键值不小于v中的数据项 的键值 堆上的运算 上移和下移 从堆中删除最大键值的数据项 插入项x到堆中 从堆中删除第i项 将一个数组转换成堆 渐近复杂性 渐近符号性质 常用函数 基本数据结构

堆(Heap) 上移运算:将第10个位置的5变成25 渐近复杂性 渐近符号性质 常用函数 基本数据结构

堆(Heap) 下移运算:将第2个位置的17变成3 渐近复杂性 渐近符号性质 常用函数 基本数据结构

堆(Heap) 插入运算:先将x添加到堆的末尾,再将x上移直到 满足堆特性为止 删除运算:要从大小为n的堆H中删除元素H[i],先 用H[n-1]替换H[i],再根据H[i]的键值与存储在父 结点和子结点中元素键值的关系,对H[i]做上移或 下移运算,直到满足堆特性 删除最大值运算:返回根结点,并将其删除即可 渐近复杂性 渐近符号性质 常用函数 基本数据结构

堆(Heap) 建堆运算:从最后一个结点开始到根结点,逐个扫 描所有的结点,每一次将以当前结点为根结点的子 树转换成堆 初始化 第一步调整 渐近复杂性 渐近符号性质 常用函数 基本数据结构

堆(Heap) 建堆运算:从最后一个结点开始到根结点,逐个扫 描所有的结点,每一次将以当前结点为根结点的子 树转换成堆 第二步调整 第三步调整 渐近复杂性 渐近符号性质 常用函数 基本数据结构

堆(Heap) 建堆运算:从最后一个结点开始到根结点,逐个扫 描所有的结点,每一次将以当前结点为根结点的子 树转换成堆 第四步调整 渐近复杂性 渐近符号性质 常用函数 基本数据结构

课后思考 尝试证明树的几个性质 令T是非空二叉搜索树,设计从T中删除或插入元素x的 算法,并分析其时间复杂性 写一个算法将两个同样大小的堆合并为一个,分析算法 的计算复杂性 渐近复杂性 渐近符号性质 常用函数 基本数据结构