GESP 八级 · GESP 202506 C++ 八级 第 7 题

$n$ 个结点的二叉树，执行广度优先搜索的平均时间复杂度是（ ）。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】广度优先搜索｜二叉树遍历｜时间复杂度分析

1. 考纲定位：本题出自 GESP 八级"数据结构与算法"模块的"树与图遍历"部分。命题人把 BFS 时间复杂度放在这里，就是为了打那些只背结论的考生——他们常把 BFS 和二分查找的 O(log n) 混淆，或者把遍历所有节点误算成 O(n log n)。

2. 解题思维：BFS 用队列逐层展开，每个节点恰好入队一次、出队一次，无论树是平衡还是退化成链。所以总操作数与节点数 n 成正比，即 O(n)。关键观察是"遍历"的本质：必须访问所有节点，顺序不影响总次数。

3. 陷阱拆解：选 A 的同学把 BFS 当成二分查找，却忘了二叉树的高度只是 O(log n) 的前提是平衡树，而遍历仍要访问全部节点；选 B 的同学把 BFS 和排序算法混为一谈，误以为每层都要排序；选 D 的同学把 BFS 和回溯法混淆，以为会枚举所有子集。最阴险的细节是"平均"二字，诱导考生想"平均树是平衡的，所以高度 log n"，但遍历复杂度只取决于节点数，与树形无关。

4. 反命题思维：若命题人想考二叉树遍历，可能会问"后序遍历的时间复杂度"或"递归 DFS 的时间复杂度"；若考完全二叉树，可能问"BFS 的空间复杂度"。刷到类似题时，先问自己：命题人想考我什么——是算法复杂度、数据结构特性，还是遍历顺序？