Предполагается, что у нас есть неориентированный граф, а список смежности реализован в виде массива связанных списков. Из Википедии я вижу следующие временные сложности для Списка смежности:
- Добавление вершины -
O(1) - В этот ответ , автор говорит, что с массивами сложность амортизированного времени равна
O(1), поскольку наихудший случай должен быть редким. Это не имеет смысла для меня. Поскольку массив имеет фиксированный размер (равный количеству вершин), я бы подумал, что добавление вершины всегда будет означать создание нового массива большего размера и копирование элементов из старого массива в новый массив, который должен быть O(|V|).
- Удалить вершину -
O(|E|) - В этот ответ , Автор утверждает, что временная сложность удаления вершины составляет
O(deg(V)) = O(V). Это не соответствует тому, что перечислено в Википедии. Мой мыслительный процесс заключается в том, что для удаления вершины нам нужно будет выполнить итерацию по всем вершинам, и для каждой вершины проверяется наличие края удаляемой вершины. Это должно быть O(V) * O(V+E) = O(V^2).
Буду признателен, если кто-нибудь сможет уточнить. Спасибо.