在大多數教科書中，UCS 最壞情況運行時間的漸近上限定義為 O(b(1 C / ε))。詳細資訊在這里解釋：統一成本搜索的時間復雜度。
O(b(1 C / ε)) 反映了 UCS 在找到特定目標狀態之前必須探索的狀態總數的上限。通常所有這些狀態都存盤和維護在一個最小優先級佇列（邊界）中。
我想知道為什么在定義 UCS 的時間復雜度時沒有明確考慮維護最小優先級佇列的開銷。讓我們定義 n = b(1 C / ε)。那么不應該是運行時間O(nlgn)嗎？
為什么沒有明確包含 lgn？是因為我們在關注漸近行為時可以忽略它嗎？
uj5u.com熱心網友回復：
這里的“問題”實際上與演算法無關，而是 CS 的不同子欄位對事物使用不同的名稱（有時對不同的事物使用相同的名稱）。這完全是定義不同的情況。
“統一成本搜索”是 Dijkstra 演算法變體的另一個名稱，通常用于 AI 的背景關系中，其中底層圖可能是無限的。正如您所提到的，您提供的鏈接和來自該鏈接的 AI 教科書計算出O(b^(1 C / ε))UCS 探索了節點，這是正確的。然而，該演算法在計算機上進行的基本操作的數量（這是計算復雜性理論中常用的度量）將包括一個對數因子來處理優先級佇列操作。如果您通過基本運算測量運行時間，那么在漸近法中絕對不能忽略log n 因子。
由于您參考的教科書是 AI 教科書，因此僅順便提及優先級佇列，因為重點不是資料結構及其運行時的各種實作。他們指出，在比較演算法的時間復雜度時，他們只計算探索的狀態數，因為這是教科書的重點。另一方面，“演算法導論”教科書中的處理將討論實作和斐波那契堆，并使用不同的時間復雜度度量。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/335905.html
下一篇：無法訪問裝飾函式內的函式屬性