12.23用树、DAG表示表达式
有向图的顶点的度等于该顶点的入度与出度之和。
因此对于邻接表,某个顶点的链表为空,该顶点出度为0。
对于逆邻接表,某个顶点的链表为空,该顶点入度为0。
一个有向图D=(V, A)满足什么条件是V到V的一个映射的图?
A对任意 v∈V, od(v)=1;
从Vi到Vj的映射,是指对于V中的每一个元素i,V中都有一个唯一的元素j与之对应,也就是 i--->j 唯一,出度=1。就是说要么一对一,要么一对多,要形成唯一确定的关系,每个点都只能由一个点确定
入度为1,正是DAG的特点,
即理解为只能由一个唯一的点确定,或者前驱只有一个
拓扑排序,事件的先后关系,正是体现在唯一的紧邻前驱上
用树、DAG表示表达式
用有向无环图描述表达式 (A+B)*((A+B)/A), 至少需要顶点的数目为 ( 5)
用DAG表述,首先是要得到二叉树的表示,然后采用拓扑排序的方法,结合、化简掉中间过程中出现的一些部分,从而实现化简.实际就是一个去重的过程
大顶堆中除了堆顶元素是最大值,其余元素的顺序都是无法确定的。
堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。时间复杂度O(n*logn) 如果从底部最后的父节点开始建堆,那么我们可以大概算一下: 假如有N个节点,那么高度为H=logN,最后一层每个父节点最多只需要下调1次,倒数第二层最多只需要下调2次,顶点最多需要下调H次,而最后一层父节点共有2^(H-1)个,倒数第二层公有2^(H-2),顶点只有1(2^0)个,所以总共的时间复杂度为s = 1 * 2^(H-1) + 2 * 2^(H-2) + ... + (H-1) * 2^1 + H * 2^0 将H代入后s= 2N - 2 - log2(N),近似的时间复杂度就是O(N)。
如果堆的有序状态因为某个节点变得比它的父节点更大而打破,那么就需要通过交换它和它的父节点来修复堆。从最后一个非叶结点逐渐往上浮,直到有序。
根元素为最小值的二叉堆:
插入节点时间复杂度为O(log n)
删除节点时间复杂度为O(log n)
查询最小元素的复杂度是o(1)
合并两个堆的复杂度是o(lgn)
对于有n(n>3)个不重复元素的大顶堆,下标为n-2的元素和下标为n-1的元素的大小关系是()
因为只有堆顶元素是确定的最大值,对于末尾元素,只有小于父节点这一个条件;因此它们的大小关系无法确定。
创建堆的基本思想:先把无序的关键字按顺序构造成完全二叉树,从最后一个分支节点开始往前,不断地利用筛选算法,将一棵棵子树调整为一个堆,一直进行到完全二叉树的根节点为止。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!