n叉树广度优先搜索(BFS)时间复杂度分析及O(n)算法咨询
n叉树BFS算法时间复杂度解析及替代实现
现有代码的复杂度判定
你给出的这段BFS实现时间复杂度为O(n),并非O(n²),原因如下:
- 算法运行全程,每个树节点只会执行1次入队、1次出队操作,这部分总操作量和节点总数n成正比。
- 内层遍历子节点的循环,总执行次数等于整棵树的总边数,而n个节点的树无论分叉数多少,总边数固定为n-1,这部分操作量同样和n成正比。
两部分操作叠加的总计算量是线性的,因此时间复杂度为O(n)。
注意:该结论成立的前提是你使用的
Queue实现的enqueue、dequeue方法都是O(1)时间复杂度。如果你是用JavaScript普通数组的shift方法模拟出队,每次出队需要移动数组内所有剩余元素,时间复杂度为O(k),整体算法复杂度会退化到O(n²)。
O(n)复杂度的替代实现
如果你不想引入自定义Queue实现,可以用按层迭代的方式实现BFS,复杂度同样为O(n):
const breadthFirstSearch = (root, output = []) => { if (!root) return output; let currentLayer = [root]; while (currentLayer.length) { const nextLayer = []; for (const node of currentLayer) { output.push(node.val); nextLayer.push(...node.children); } currentLayer = nextLayer; } return output; };
该实现不需要额外的队列数据结构,每层节点批量处理,所有节点仅会被遍历一次,满足线性时间复杂度要求。
内容的提问来源于stack exchange,提问作者MOE
相关产品推荐
相关产品推荐

