You need to enable JavaScript to run this app. n叉树广度优先搜索(BFS)时间复杂度分析及O(n)算法咨询
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.16 09:45:05