Frage

Why is storage image 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?

War es hilfreich?

Lösung

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).

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top