Относительно памяти алгоритма Флойда-Варшалла O(n^2)

Question

Относительно памяти алгоритма Флойда-Варшалла O(n^2)

Почему хранение образ в алгоритме Флойда-Варшалла? Не было бы меньше, если бы использовался связанный список, а не матрица N на N?

1

graph-theory computer-science-theory

Источник

user821557 26 июл '13 в 01:47

1 ответ

Решение

Другие вопросы по тегам graph-theory computer-science-theory

user178382 26 июл '13 в 01:53 2013-07-26 01:53 · Accepted Answer · 2013-07-26 01:53

Наихудший размер этого связанного списка все равно будет O(n^2) (Я думаю? Я не совсем уверен, что понимаю, как вы предлагаете его использовать), но стоимость поиска будет достаточно дорогой, чтобы изменить асимптотическую сложность всего алгоритма (операции со связанными списками не имеют такой же сложности, как операции на матрицах известного размера).