Я работал над некоторыми вопросами по Leetcode для алгоритма Дейкстры и не совсем понимаю его пространственную сложность. Я поискал в Интернете, но нашел разные ответы, некоторые из которых были довольно сложными, поэтому мне хотелось узнать, правильно ли я их понял.
Код: Выделить всё
# initialize maxheap
maxHeap = [(-1, start_node)]
heapq.heapify(maxHeap)
# dijkstras algorithm
visit = set()
res = 0
while maxHeap:
prob1,cur = heapq.heappop(maxHeap)
visit.add(cur)
# update result
if cur == end_node:
res = max(res, -1 * prob1)
# add the neighbors to the priority queue
for nei,prob2 in adj_list[cur]:
if nei not in visit: heapq.heappush(maxHeap, (prob1 * prob2, nei))
Поскольку я использую набор посещений и очередь приоритетов для отслеживания узлов, сложность пространства будет просто равна O(V), где V — это количество вершин в графе? И если бы мне пришлось создать список смежности в Python с помощью dict, имела бы пространственная сложность O(E), где E — количество ребер?
Подробнее здесь:
https://stackoverflow.com/questions/788 ... f-dijkstra