在大多数教科书中，UCS的最坏情况运行时间的渐近上界定义为O(b(1 + C/ε))。详细说明如下:统一成本搜索的时间复杂度。
O(b(1 + C/ε))反映了UCS在找到特定目标状态之前必须探索的状态总数的上界。通常，所有这些状态都存储并维护在最小优先级队列(边界)中。
我想知道为什么在定义UCS的时间复杂度时没有显式地考虑维护最小优先级队列的开销。我们定义n = b(1 + C/ε)那么运行时间不应该是O(nlgn)吗?
为什么没有显式包含lgn ?是因为我们在关注渐近行为时可以忽略它吗?
这里的"问题"不是关于算法，而是CS的不同子字段使用不同的名称(有时相同的名称用于不同的事物)。这完全是一个不同定义的情况。
"均匀代价搜索"是Dijkstra算法的另一种变体，通常用于底层图可能是无限的人工智能环境中。如您所述，您提供的链接和该链接中的AI教科书计算出UCS探索了O(b^(1 + C / ε))节点，这是正确的。然而，算法在计算机上执行的基本操作的数量(这是计算复杂性理论中常用的度量)将包含一个对数因子来处理优先级队列操作。如果您通过基本操作来度量运行时间，那么log n因子绝对可以而不是在渐近中被忽略。
因为你引用的教科书是一本人工智能教科书，所以优先级队列只是顺便提到的，因为重点不是数据结构的各种实现及其运行时。他们指出，在比较算法的时间复杂度时，他们只计算所探索的状态数，因为这是教科书的重点。另一方面，"算法导论"教科书中的处理方法将讨论实现和斐波那契堆，并使用不同的时间复杂度度量。