Анализ алгоритма несвязанного краевого поиска

Question

У меня есть алгоритм для нахождения набора непересекающихся контуров пути в неориентированном графе.

1. Start со списком всех ребер в графе

2. Хотя все еще доступны края в списке, выполните глубину/вширь первый поиск, чтобы найти путь. Если путь найден, сохраните его, удалить ребра из обоего списка и график и путь приращения счетчика

3. Удалить первый доступный край из списка и назначить его текущего пути

4. Try, чтобы соответствовать текущему пути к списку сохраненных края

5. Если не имеющийся край не совпадает, путь закончен

6. Если доступный край может продлить текущий путь, добавьте его в текущий путь и удалить из списка края, а затем продолжать пытаться продлить текущий путь.

Я считаю, что 2 и 3 выполняются в O (Е (V + E) + E) время, потому что

• ширина/глубина первый поиск выполняется в O (V + Е) Время
• поиска выполняется по электронным кромкам в списке
• удаления E кромки из списка и графа

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

Таким образом, у меня есть окончательный худший случай O (Е (V + Е) + E^2 + E) = O (EV + 2е^2 + Е)

Я прав?

Answer 1

Нет, это не так. Насколько я понимаю, ваша проблема O (E (V + E) + E^2 + E) правильна. Но в Big O Notation можно было бы принять «самое большое» событие для сложности. У вас есть три класса сложности в нем:

1. E (V + E)
2. E^2
3. E

Пункт 3 исключается пунктом 2, потому что два больше в каждом дело. В «худшем случае» E есть V^2. С учетом этого вы можете определить, что точка 1 является самой большой частью сложности (V^3 + V^4> V^4). Ваш алгоритм является правильным, ваши предположения о частях, так что алгоритмическая сложность этой задачи будет: O (E (V + E))

Вы можете взглянуть на эти slides. На слайде 23 сложность записывается и соответствует вашим расчетам;)