我正在閱讀關于圖形實作的 Python 模式文章，并遇到了討論尋找最短路徑的最佳實作的部分。文章在這里。
我無法理解這兩個任務之間的區別dist[next]；后者在運行時是二次的，但前者是線性的？
線性運行時間：
# Code by Eryk Kopczyński
def find_shortest_path(graph, start, end):
dist = {start: [start]}
q = deque(start)
while len(q):
at = q.popleft()
for next in graph[at]:
if next not in dist:
dist[next] = [dist[at], next] # this line
q.append(next)
return dist.get(end)
二次運行時：
# Code by Eryk Kopczyński
def find_shortest_path(graph, start, end):
dist = {start: [start]}
q = deque(start)
while len(q):
at = q.popleft()
for next in graph[at]:
if next not in dist:
dist[next] = dist[at] [next] # this line
q.append(next)
return dist.get(end)
有人可以解釋一下這兩個任務之間有什么區別嗎？
uj5u.com熱心網友回復：
[ ]括號表示法用于下標取消參考和構造串列。
您詢問了這些表達方式：
dist[next] = [dist[at], next]
dist[next] = dist[at] [next]
讓我們忽略賦值的 LHS 左側，因為它只是存盤一個 dict 映射。而不是dist[next] = ...
它可以很容易地x = ...
被dist[next] = x.
同樣，在 RHS 中讓我們忽略dist[at]. 我們可以很容易地預先設定一個 temp var: y = dist[at]，然后y在運算式中使用。
好的，不影響方括號符號，讓我們關注構造[y, next]和y [next]運算式的演算法復雜性，其中y是串列。
我們可以在 O(1) 恒定時間內計算第一個運算式。y我們只需分配一個短串列并用指向物件的指標填充其前兩個元素next。
第二個串列運算式y [next]需要掃描 的每個元素y并將其復制到一個新的臨時結果中，然后最后附加一個next指向該結果的指標。y如果長度為，則這具有 O(n) 線性成本n。
解釋
為什么需要額外的作業？好吧，假設一個元素y隨后發生了突變，更改為一個新值。第一個運算式很好，它將反映新值，因為程式員要求在串列中存盤一個指標，即對y所指向內容的參考。
OTOH 第二個運算式不會保留這種關系，它只查看加號兩側的值。 想象一下，我們存盤那個“大串列”結果，然后 mutate y。對大名單沒有影響，這是應該的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/479561.html