广度遍历到某个dom的时间复杂度

Question

老师这是国内某家大公司的面试题，看完递归复杂度分析做这个题有了点思路，大概是假如某个dom节点在第n层的第m个，再算上前面n-1层需要全部遍历完，那复杂度可以近似看成是(n-1)^2+m吗？请老师指教

Answer 1

liuyubobobo 2018-01-08 13:05:08

通常在遍历算法中，我们把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，可以回忆一下等比数列公式，如何化简？不过依然是，我们一般不这么表达遍历的时间复杂度。

• 提问者 哈哈哈蜜瓜 #1

  老师你给出的a是每一个父节点下面有a个子节点，这样的话就好算很多，但是如果不同的父节点下面的子节点个数都不尽相同那应该怎么算？

• liuyubobobo 回复 提问者 哈哈哈蜜瓜 #2

  时间复杂度算的是上界，上界就是所有的节点都有a个子树。其中a是节点拥有的最大子树个数。当然，这样算的上界不够紧，所以一般还是用n表达节点总数，对树的遍历的时间复杂度就是O(n)。

• 提问者 哈哈哈蜜瓜 回复 liuyubobobo #3

  感谢老师！