在用邻接表表示图时,拓扑排序算法时间复杂度为()
A.O(n)
B.O(n*n*n)
C.O(n*n)
D.O(n+e)
正确答案是 D
若为避免重复检测入度为零的顶点,使用栈来保存所有入度为零的顶点。对有n个顶点和e条弧的有向图而言,建立求各顶点的入度的时间复杂度为O(e);建零入度顶点栈的时间复杂度为O(n);在拓扑排序过程中,若有向图无环,则每个顶点进一次栈,出一次栈,入度减一的操作在while循环中总共执行e次,所以总的时间复杂度为O(n+e)。
很基础的题,但还是要细心才能做对
拓扑排序结果不唯一,可以判断是否有环,针对有向图。时间复杂度为O(n+e),空间复杂度为O(n)。
一棵具有n个结点的二叉树,若它有m个叶子结点,则该二叉树中度为1的结点个数是多少?
某公园内有个奇怪的摊主小周,他只在星期一、星期二、星期三、星期五和星期六工作,而且他只出售4种商品:玩具汽车、充气气球、橡皮泥和遥控飞机。<
请实现KMP算法?
请你谈谈Cookie的弊端
很基础的题,但还是要细心才能做对
拓扑排序结果不唯一,可以判断是否有环,针对有向图。时间复杂度为O(n+e),空间复杂度为O(n)。