统一成本搜索的时间复杂度（包括最小优先级队列）
Time Complexity of Uniform Cost Search (Including Min Priority Queue)
在大多数教科书中，UCS最坏情况运行时间的渐近上界定义为O(b(1 + C / ε))。详细说明在这里：Time complexity of Uniform-cost search.
O(b(1 + C / ε)) 反映了 UCS 在找到特定目标状态之前必须探索的状态总数的上限。通常所有这些状态都存储和维护在一个最小优先级队列（边界）中。
我想知道为什么在定义 UCS 的时间复杂度时没有明确考虑维护最小优先级队列的开销。让我们定义 n = b(1 + C / ε)。那不应该是运行时间O(nlgn)吗？
为什么没有明确包含 lgn？是因为我们关注渐近行为时可以忽略它吗？
这里的'problem'并不是真正关于算法的，而是CS的不同子领域对事物使用不同的名称（有时对不同的事物使用相同的名称）。这完全是定义不同的情况。
'Uniform cost search' 是 Dijkstra 算法变体的另一个名称，通常用于 AI 的上下文中，其中底层图可能是无限的。正如您提到的，您提供的 link 和 link 中的 AI 教科书计算出 UCS 探索了 O(b^(1 + C / ε)) 个节点，这是正确的。然而，算法在计算机上进行的基本操作的数量（这是计算复杂性理论中通常使用的度量）将包括一个对数因子来处理优先级队列操作。如果您通过基本运算测量 运行 时间，log n 因子绝对 不会 在渐近中被忽略。
由于您引用的教科书是一本人工智能教科书，优先级队列只是顺便提到，因为重点不是数据结构的各种实现及其运行时。他们指定在比较算法的时间复杂度时，他们只计算探索的状态数，因为这是教科书的重点。另一方面，'Introduction to algorithms' 教科书中的处理会讨论实现和斐波那契堆，并使用不同的时间复杂度度量。
在大多数教科书中，UCS最坏情况运行时间的渐近上界定义为O(b(1 + C / ε))。详细说明在这里：Time complexity of Uniform-cost search.
O(b(1 + C / ε)) 反映了 UCS 在找到特定目标状态之前必须探索的状态总数的上限。通常所有这些状态都存储和维护在一个最小优先级队列（边界）中。
我想知道为什么在定义 UCS 的时间复杂度时没有明确考虑维护最小优先级队列的开销。让我们定义 n = b(1 + C / ε)。那不应该是运行时间O(nlgn)吗？
为什么没有明确包含 lgn？是因为我们关注渐近行为时可以忽略它吗？
这里的'problem'并不是真正关于算法的，而是CS的不同子领域对事物使用不同的名称（有时对不同的事物使用相同的名称）。这完全是定义不同的情况。
'Uniform cost search' 是 Dijkstra 算法变体的另一个名称，通常用于 AI 的上下文中，其中底层图可能是无限的。正如您提到的，您提供的 link 和 link 中的 AI 教科书计算出 UCS 探索了 O(b^(1 + C / ε)) 个节点，这是正确的。然而，算法在计算机上进行的基本操作的数量（这是计算复杂性理论中通常使用的度量）将包括一个对数因子来处理优先级队列操作。如果您通过基本运算测量 运行 时间，log n 因子绝对 不会 在渐近中被忽略。
由于您引用的教科书是一本人工智能教科书，优先级队列只是顺便提到，因为重点不是数据结构的各种实现及其运行时。他们指定在比较算法的时间复杂度时，他们只计算探索的状态数，因为这是教科书的重点。另一方面，'Introduction to algorithms' 教科书中的处理会讨论实现和斐波那契堆，并使用不同的时间复杂度度量。