在大多数教科书中，均匀成本搜索（UCS）最坏情况运行时间的渐进上界被定义为O(b(1 + C / ε))。详细说明请见此处：均匀成本搜索的时间复杂度。

O(b(1 + C / ε))反映了UCS在找到特定目标状态之前必须探索的总状态数的上界。通常，所有这些状态都被存储并维护在一个最小优先级队列（前沿）中。

我想知道为什么在定义UCS的时间复杂度时，没有明确考虑维护最小优先级队列的开销。让我们定义n = b(1 + C / ε)。那么运行时间不应该是O(nlgn)吗？

为什么没有明确包含lgn？是因为在关注渐进行为时可以忽略它吗？

回答：

这里的“问题”实际上并不在于算法本身，而是计算机科学的不同子领域对事物使用不同的名称（有时对不同的事物使用相同的名称）。这完全是定义不同的问题。

“均匀成本搜索”是Dijkstra算法的一个变体的另一个名称，通常在人工智能的背景下使用，其中底层图可能为无限。如你所提到的，你提供的链接和该链接中的AI教科书计算出UCS探索的节点数为O(b^(1 + C / ε))，这是正确的。然而，算法在计算机上执行的基本操作数（这是计算复杂性理论中通常使用的度量）将包括一个对优先级队列操作进行处理的对数因子。如果你通过基本操作来衡量运行时间，对数因子在渐进分析中绝对不能被忽略。

由于你引用的教科书是一本AI教科书，优先级队列只是被提及，因为重点不在于数据结构的各种实现及其运行时间。他们指定在比较算法的时间复杂度时，只计算探索的状态数，因为这是教科书的重点。另一方面，一本“算法导论”教科书的处理方式会讨论实现和Fibonacci堆，并使用不同的时间复杂度度量。