含最小优先队列的一致代价搜索时间复杂度未含lgn项疑问

你提到的O(b(1 + C / ε))本质是UCS需要扩展的节点总数的渐近上界，不是包含底层数据结构操作的总运行时间上界，这是AI搜索算法领域的常用分析惯例，核心原因有两个：

• 入门教材分析搜索算法复杂度时，通常优先统计节点扩展数量这个核心指标，方便和BFS、DFS、A*等其他搜索算法做横向对比。比如BFS的时间复杂度写O(b^d)的时候，也是只统计节点数，没有把普通队列的O(1)入队出队开销单独拎出来写，UCS的分析沿用了这个统一的度量标准。
• 优先队列的开销属于实现层面的变量，没有统一的固定值：
  • 如果用普通二叉堆实现，每次弹出最小元素的开销是O(lg n)，那总运行时间确实是O(n lg n)（其中n = b(1 + C / ε)），这个时候对数项不能忽略；
  • 如果用斐波那契堆实现优先队列，减小键值的操作是摊还O(1)，仅弹出最小元素需要O(lg n)，总开销会比二叉堆实现低很多；
  • 如果是边权为小范围整数的特殊场景，还可以用桶队列实现优先队列，所有操作都是O(1)，总运行时间就和节点扩展数的上界完全一致。

如果是做工程实现的性能预估，你需要把优先队列的开销纳入计算，不能直接套用教材里的节点数上界；但如果是做搜索策略本身的效率对比，只看节点扩展数的上界就足够判断不同算法的搜索范围差异。

内容的提问来源于stack exchange，提问作者Florian Bär