Download presentation
Presentation is loading. Please wait.
1
Algorithm Design and Analysis
计算机科学与技术专业课程 Algorithm Design and Analysis 算法设计与分析 宋传鸣 辽宁师范大学计算机与信息技术学院
2
渐近复杂性(Asymptotic Complexity)
定义:对于T(n),如果存在 ,使得当 时有 则称 是T(n)当 时的渐近性态, 也称算法的渐近复杂性 直观上,T(n)是 略去低阶项后所留下的主项 用法 当问题规模充分大时,只需考察算法再渐近性态下的复杂性 它是T(n)的一种简化,目的在于比较两个具有不同阶复杂性的算法的效率 渐近复杂性 渐近符号性质 常用函数 基本数据结构
3
渐近分析的记号 渐近上界记号O: 如果存在正常数c 和 使得当 时,有 ,则称函数f(n)当n充分大时有上界,且g(n)是它的一个上界,记为
非紧上界记号o:如果对于 ,都存在 使 得当 时,有 ,则称函数f(n)当n充 分大时的阶比g(n)低,记为 渐近复杂性 渐近符号性质 常用函数 基本数据结构
4
渐近分析的记号 非紧下界记号ω:如果对于 ,都存在 使 得当 时,有 ,则称函数f(n)当n充分 大时的阶比g(n)高,记为
四种记号含义的比较 O与o类似,主要区别在于:满足o的函数集合的势要大于满足O的函数集合的势 同理,Ω与ω类似 在评价算法的复杂性时,上界的阶越低,下界的阶越高,则评估越精确,结果越有价值 渐近复杂性 渐近符号性质 常用函数 基本数据结构
5
渐近分析的记号 紧渐近界记号θ:如果存在正常数c1,c2和 使 得当 时,有 ,则称函数f (n)当n充分大时与g(n)同阶,记为
定理: 当且仅当 并且 渐近复杂性 渐近符号性质 常用函数 基本数据结构
6
渐近分析记号的若干性质 传递性 并且 ,则 自反性 对称性 当且仅当 渐近复杂性 渐近符号性质 常用函数 基本数据结构
7
渐近分析记号的若干性质 转置对称性 渐近分析记号的算术运算 渐近分析的作用 当且仅当 如果 ,则 ,其中c为一个正常数
如果 ,则 ,其中c为一个正常数 渐近分析的作用 考察解决同一问题的不同算法的复杂性界限 渐近复杂性 渐近符号性质 常用函数 基本数据结构
8
渐近复杂性分析中的常用函数 取整函数 取整函数的性质 :不大于x的最大整数 :不小于x的最小整数 对于n≧0, 有 渐近复杂性 渐近符号性质
基本数据结构
9
渐近复杂性分析中的常用函数 多项式函数 指数函数 定义: 若对于某个常数k,有 ,则称其有多项式界 对于 , 且 ,有 ,则 渐近复杂性
对于 , 且 ,有 ,则 渐近复杂性 渐近符号性质 常用函数 基本数据结构
10
渐近复杂性分析中的常用函数 指数函数 渐近复杂性 渐近符号性质 常用函数 基本数据结构
11
渐近复杂性分析中的常用函数 对数函数 定义:
若对于某个常数k,有 ,则称其多项式对数有界(Polylogarithmically bounded) 对于 渐近复杂性 渐近符号性质 常用函数 基本数据结构
12
渐近复杂性分析中的常用函数 阶乘函数 定义: 斯特林(Stirling)近似公式 由此可知 渐近复杂性 渐近符号性质 常用函数 基本数据结构
13
不同渐近函数之间的关系 小规模数据 渐近复杂性 渐近符号性质 常用函数 基本数据结构
14
不同渐近函数之间的关系 中等规模数据 渐近复杂性 渐近符号性质 常用函数 基本数据结构
15
渐近复杂性分析中的常见公式 二项式系数 设n为正整数, 则有 令x=1,有 令x=－1,有 渐近复杂性 渐近符号性质 常用函数 基本数据结构
16
渐近复杂性分析中的常见公式 鸽巢原理 和式 如果把n个球分别放在m个盒子中,那么 存在一个盒子必定至少装 个球 存在一个盒子必定最多装 个球
存在一个盒子必定至少装 个球 存在一个盒子必定最多装 个球 和式 算术级数: 平方和: 几何级数: 渐近复杂性 渐近符号性质 常用函数 基本数据结构
17
渐近复杂性分析中的常见公式 和式 几何级数: 对几何级数两边求导,得到 当c=2时,有 当c=1/2时,有 渐近复杂性 渐近符号性质
常用函数 基本数据结构
18
渐近复杂性分析中的常见公式 求和的积分近似 如果f(x)是单调递减的连续函数,则 渐近复杂性 渐近符号性质 常用函数 基本数据结构
19
渐近复杂性分析中的常见公式 求和的积分近似 如果f(x)是单调递增的连续函数,则 示例:求和式 和调和级数 的上下界 渐近复杂性
示例:求和式 和调和级数 的上下界 渐近复杂性 渐近符号性质 常用函数 基本数据结构
20
渐近复杂性分析举例 求和 第4步的执行次数为 渐近复杂性 渐近符号性质 常用函数 基本数据结构
21
渐近复杂性分析举例 求和 第5步的执行次数为 渐近复杂性 渐近符号性质 常用函数 基本数据结构
22
渐近复杂性分析中的常用函数 摘自 e&uid=324529&do=blog&id=386663 渐近复杂性 渐近符号性质 常用函数 基本数据结构
23
链表(List) 由有限的元素或结点序列组成,结点包含数据域和 到另一个结点的链域 单链表 循环链表 双向链表 循环双向链表
堆栈:只允许在一端进行插入和删除运算的链表 队列:只允许在一端进行插入运算,而在另一端进行删除运算 渐近复杂性 渐近符号性质 常用函数 基本数据结构
24
树(Tree) 树是n(n≥0)个结点的有限集T,T为空时称为空树, 否则它满足如下两个条件: 有且仅有一个特定的称为根(Root)的结点
其余的结点可分为m(m≥0)个互不相交的子集,其中每个子集本身又是一棵树,并称其为根的子树 渐近复杂性 渐近符号性质 常用函数 基本数据结构
25
树(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 树的高度或深度:树中结点的最大层数 渐近复杂性 渐近符号性质 常用函数 基本数据结构
26
树(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,最小是 渐近复杂性 渐近符号性质 常用函数 基本数据结构
27
树(Tree) 二叉树的遍历 前序:访问结点的操作发生在遍历其左右子树之前 中序:访问结点的操作发生在遍历其左右子树之间
后序:访问结点的操作发生在遍历其左右子树之后 渐近复杂性 渐近符号性质 常用函数 基本数据结构
28
树(Tree) 二叉搜索树 所有存储在顶点v的左子树中的元素都小于存储在v中的元素,所有存储在顶点v的右子树中的元素都大于存储在v中的元素
用二叉搜索树表示一个集合并不是唯一的 渐近复杂性 渐近符号性质 常用函数 基本数据结构 4 6 8 9 1 3 6 3 8 1 4 9
29
图(Graph) 图G由一个顶点集合V和一个边集合E组成 有向图和无向图 图的表示:邻接矩阵或邻接表 渐近复杂性 渐近符号性质 常用函数
基本数据结构
30
图(Graph) 图的遍历 深度优先遍历:尽可能先对纵深方向进行搜索 广度优先遍历:尽可能先对横向进行搜索 渐近复杂性 渐近符号性质
常用函数 基本数据结构
31
堆(Heap) 一个堆是一个几乎完全的二叉树,它的每个结点都 满足:如果v和p(v)分别是结点和它的父结点,那么 存储在p(v)中的数据项的键值不小于v中的数据项 的键值 堆上的运算 上移和下移 从堆中删除最大键值的数据项 插入项x到堆中 从堆中删除第i项 将一个数组转换成堆 渐近复杂性 渐近符号性质 常用函数 基本数据结构
32
堆(Heap) 上移运算:将第10个位置的5变成25 渐近复杂性 渐近符号性质 常用函数 基本数据结构
33
堆(Heap) 下移运算:将第2个位置的17变成3 渐近复杂性 渐近符号性质 常用函数 基本数据结构
34
堆(Heap) 插入运算:先将x添加到堆的末尾,再将x上移直到 满足堆特性为止
删除运算:要从大小为n的堆H中删除元素H[i],先 用H[n-1]替换H[i],再根据H[i]的键值与存储在父 结点和子结点中元素键值的关系,对H[i]做上移或 下移运算,直到满足堆特性 删除最大值运算:返回根结点,并将其删除即可 渐近复杂性 渐近符号性质 常用函数 基本数据结构
35
堆(Heap) 建堆运算:从最后一个结点开始到根结点,逐个扫 描所有的结点,每一次将以当前结点为根结点的子 树转换成堆 初始化 第一步调整
渐近复杂性 渐近符号性质 常用函数 基本数据结构
36
堆(Heap) 建堆运算:从最后一个结点开始到根结点,逐个扫 描所有的结点,每一次将以当前结点为根结点的子 树转换成堆 第二步调整
第三步调整 渐近复杂性 渐近符号性质 常用函数 基本数据结构
37
堆(Heap) 建堆运算:从最后一个结点开始到根结点,逐个扫 描所有的结点,每一次将以当前结点为根结点的子 树转换成堆 第四步调整
渐近复杂性 渐近符号性质 常用函数 基本数据结构
38
课后思考 尝试证明树的几个性质 令T是非空二叉搜索树,设计从T中删除或插入元素x的 算法,并分析其时间复杂性
写一个算法将两个同样大小的堆合并为一个,分析算法 的计算复杂性 渐近复杂性 渐近符号性质 常用函数 基本数据结构
Similar presentations
