Сложность времени и сложности матрицы смежности и списка смежности

Question

Я читаю «Дизайн алгоритмов». Эва Тардос и в главе 3 упоминается, что матрица смежности имеет сложность O(n^2), а список смежности имеет O(m+n), где m - общее число ребрами и n - общее число узлов. В нем говорится, что в случае списка смежности нам понадобятся только списки размера m для каждого узла.

Не получится ли что-то похожее на матрицу в случае списка смежности, поскольку у нас есть списки, которые также являются 1D-массивами. Так что в основном это O(m*n) по мне. Пожалуйста, направляйте меня.

Answer 1

Смежная матрица сохраняет значение (1/0) для каждой пары узлов, независимо от того, существует ли край или нет, поэтому для этого требуется пространство n*n.

Прилегающий список содержит только существующие ребра, поэтому его длина не превышает число ребер (или количество узлов в случае, если меньше ребер, чем узлов).

В нем говорится, что в случае списка смежности нам понадобятся только списки размером м для каждого узла.

Я думаю, вы не поняли эту часть. Список смежности не содержит. Список m для каждый узел, так как m - количество ребер в целом.

В полностью подключенном графе есть граница между каждой парой узлов, поэтому для списка смежности и матрицы потребуется n*n пространства, но для каждого другого случая список смежности будет меньше.