Линейное время Дейкстры на плотном графе с двоичной кучей

Question

Первый : общее время работы алгоритма Dijkstras Shortest Path составляет

, где m - количество ребер, а n - количество вершин

Секунда : число ожидаемых операций уменьшения ключа следующее

Третий : ожидаемое время работыdijkstra с бинарной кучей, которая разрешает все операции за время log (n), составляет

Но почему время работы на плотных графах линейно, если мы считаем плотный граф, если

Может ли кто-нибудь помочь с О-нотацией и вычислениями журнала здесь?

Answer 1

Во-первых, нетрудно показать, что если m - большая омега n log(n) log(log(n)), то log(n) - большая омега log(m). Следовательно, вы можете показать, что m - это большая омега n log(m) log(log(m)).

Отсюда видно, что n - это большая омега m / (log(m) log(log(m))).

Подставим это обратно в выражение, которое у вас есть в третьей точке, и мы получим, что ожидаемое время выполнения:

O(m + n log(m/n) log(n))

                   m                                                 m
    = O(m + (------------------) log(log(m) log(log(m))) log(------------------)
             log(m) log(log(m))                              log(m) log(log(m))

Отсюда вы можете развернуть все журналы продуктов в суммы журналов. Вы получите много условий. И тогда это просто вопрос демонстрации того, что каждый является O(m) или o(m). Что просто, хотя и утомительно.

Answer 2

мое решение теперь следующее