广度遍历到某个dom的时间复杂度
来源：2-5 递归算法的复杂度分析
哈哈哈蜜瓜
2018-01-08
老师这是国内某家大公司的面试题，看完递归复杂度分析做这个题有了点思路，大概是假如某个dom节点在第n层的第m个，再算上前面n-1层需要全部遍历完，那复杂度可以近似看成是(n-1)^2+m吗？请老师指教
写回答
1回答
-
通常在遍历算法中，我们把n当做是遍历的节点个数。所以广度遍历某个dom的时间复杂度为O(n)，也就是在最坏情况下，每一个节点都遍历一遍，才找到我们真正要找到的那个dom。（深度遍历同样）
这里，由于网页的dom是个树结构，所以我们可以不考虑边的数量。如果我们遍历的是一个图结构的话，深度优先遍历和广度优先遍历的时间复杂度均为O(n+e)，n为节点个数，e为边个数。
你给出的答案有问题。相当于假设前n-1层每一层节点都是O(n)这个量级。而实际对于一棵树，最“差”可以退化成链表，每一层都只有1个节点；最“好”是一棵满a叉树(每个节点有a个子树)，此时每一层的节点个数和a是成指数关系的。(根节点叫第0层的话，第0层有1个节点，第1层有a个节点，第2层有a^2个节点，第三层有a^3个节点，...，第b层有a^b个节点）。如果我们用最差情况刻画的话，如果某个dom节点在第n层第m个的话，那么这个节点在的序列位置是 1 + a + a^2 + a^3 ... + a^(n-2) + m，可以回忆一下等比数列公式，如何化简？不过依然是，我们一般不这么表达遍历的时间复杂度。
232018-01-08
相似问题
空间，时间复杂度的猜想
回答 1
时间复杂度
回答 1