Какова временная сложность алгоритма ниже?

Question

Я просто хочу получить подтверждение временной сложности алгоритма ниже.

РЕДАКТИРОВАТЬ : далее мы не предполагаем, что используются оптимальные структуры данных. Однако не стесняйтесь предлагать решения, использующие такие структуры (четко указав, какие структуры данных используются и какое благотворное влияние они оказывают на сложность).

Обозначение : далее n = | V |, m = | E |, а avg_neigh обозначает среднее число соседей любого данного узла в графе.

Предположение : график является невзвешенным, неориентированным, и у нас загружено представление списка смежности (список списков, содержащий соседей каждой вершины).

Вот что мы имеем до сих пор:

Строка 1 : вычисление степеней - это O (n), поскольку оно просто включает получение длины каждого подсписка в представлении списка смежности, то есть выполнение n O (1) операций.

Строка 3 : для нахождения наименьшего значения требуется проверка всех значений, то есть O (n). Так как он вложен в цикл while, который посещает все узлы один раз, он становится O (n ^ 2).

Строки 6-7 : удаление вершины v равно O (avg_neigh ^ 2)как мы знаем соседей v из представления списка смежности и удаление v из каждого из подсписков соседей равно O (avg_neigh). Строки 6-7 вложены в цикл while, поэтому он становится O (n * avg_neigh ^ 2).

Строка 9 : это O (1), потому что он просто включает получениедлина одного списка. Он вложен в цикл for и цикл while, поэтому он становится O (n * avg_neigh).

Сводка : общая сложность O (n) + O (n ^ 2) +O (n * avg_neigh ^ 2) + O (n * avg_neigh) = O (n ^ 2).

Примечание 1 : если длина каждого подсписка недоступна (например,Поскольку список смежности не может быть загружен в память), вычисление степеней в строке 1 равно O (n * avg_neigh), так как каждый список имеет в среднем элементы avg_neigh и имеется n подсписков. В строке 9 общая сложность становится равной O (n * avg_neigh ^ 2).

Примечание 2 : если весовой коэффициент графа, мы можем сохранить веса ребер в представлении списка смежности. Однако получение степеней в строке 1 требует суммирования по каждому подсписку и теперь равно O (n * avg_neigh), если список смежности загружен в ОЗУ, а O (n * avg_neigh ^ 2) остальное. Аналогично, строка 9 становится O (n * avg_neigh ^ 2) или O (n * avg_neigh ^ 3).

Answer 1

Существует алгоритм, который (1) распознается как реализация алгоритма 1, а (2) выполняется за время O (| E | + | V |).

Сначала рассмотрим сутьАлгоритм 1. Пока график не пуст, сделайте следующее: запишите приоритет узла с самым низким приоритетом в качестве номера ядра этого узла и удалите этот узел. Приоритет узла определяется динамически как максимум над (1) его степенью в остаточном графе и (2) номерами ядра его удаленных соседей. Обратите внимание, что приоритет узла никогда не увеличивается, так как его степень никогда не увеличивается, и сосед с более высоким приоритетом не будет удален первым. Кроме того, приоритеты всегда уменьшаются ровно на один в каждой итерации внешнего цикла.

Поддержка структуры данных, достаточная для достижения времени O (| E | + | V |), хорошо разделяется на

1. График, который, начиная с начального графа (время инициализации O (| E | + | V |)), поддерживает

   • Удаление узла (O (степень + 1), суммирование вO (| E | + | V |) по всем узлам),
   • Получение остаточной степени узла (O (1)).

2. Очередь приоритетов, которая, начиная с начальных градусов (время инициализации O (| V |)), поддерживает

   • Popping элемент минимального приоритета (O (1) амортизированный),
   • Уменьшение приоритета элемента на единицу (O (1)), но не меньше нуля.

Подходящая реализация графа использует двусвязные списки смежности. Каждое ненаправленное ребро имеет два соответствующих узла списка, которые связаны друг с другом в дополнение к предыдущим / следующим узлам, происходящим из одной вершины. Степени могут быть сохранены в хэш-таблице. Оказывается, для реализации этого алгоритма нам нужны только остаточные степени, поэтому не беспокойтесь о сохранении остаточного графа.

Поскольку приоритетами являются числа от 0 до | V |- 1, очередь корзины работает очень хорошо. Эта реализация состоит из вектора | V | -элемента двусвязных списков, где список с индексом p содержит элементы с приоритетом p. Мы также отслеживаем нижнюю границу минимального приоритета элемента в очереди. Чтобы найти элемент минимального приоритета, мы проверяем списки в порядке, начиная с этой границы. В худшем случае это стоит O (| V |), но если мы зачислим алгоритм, когда он увеличивает границу, и дебетуют его, когда граница уменьшится, мы получим схему амортизации, которая компенсирует переменные затраты на это сканирование.

Answer 2

Если выбирается структура данных, которая может поддерживать эффективный поиск минимального значения и эффективное удаление (например, самобалансирующееся двоичное дерево или min heap ), это можно сделать в O(|E|log|V|).

• Создание структуры данных в строке 1 выполняется в O(|V|) или O(|V|log|V|).
• Цикл проходит ровно один раз для каждого узла v в V.
• Для каждого такого узла необходимо просмотреть минимальное значение и настроить DS таким образом, чтобы вы могли эффективно просматривать следующую минуту на следующей итерации. Для этого требуется O(log|V|) (в противном случае вы можете выполнить сортировку кучи в o(nlogn) - примечание здесь немного обозначений ).
• Получение neighbors и удаление элементов из V и E могут быть выполнены в O(|neighbors|) с использованием эффективной реализации набора, такой как хеш-таблица . Поскольку каждое ребро и узел выбираются ровно один раз для этого шага, он суммирует все итерации в O(|V| + |E|).
• Цикл for по neighbors, опять же, суммируется с O(|E|), благодаря тому, чтокаждое ребро здесь учитывается ровно один раз.
• В этом цикле, однако, вам может потребоваться обновить p, а такое обновление стоит O(log|V|), так что это сумма O(|E|log|V|)

Это сумма O(|V|log|V| + |E|log|V|). Предполагая, что график не очень разреженный (|E| в Omega(|V|) - это O(|E|log|V|).