The worst-case size of that linked list would still be O(n^2)
(I think? I'm not entirely sure I understand how you propose to use it), but the lookup cost would be sufficiently expensive to change the asymptotic complexity of the overall algorithm (operations on linked lists do not have the same complexity as operations on matrices of known size).
Regarding the Floyd-Warshall algorithm's O(n^2) storage
-
04-06-2022 - |
Frage
Why is storage in the Floyd-Warshall algorithm? Wouldn't it be less than that if a linked-list was used as opposed to an N by N matrix?
Lösung
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow