Число краев в разреженном графике?

Я читал Dijkstras Algorithm в гл. 24 и запутался со значением разреженного графа. Они говорят: «Если граф достаточно разрежен, в частности, E= o(V^2/lg V) -we может улучшить алгоритм, реализуя очередь с минимальным приоритетом с помощью двоичного minheap».Число краев в разреженном графике?

Мои вопросы

откуда они получены выражения E= o(V^2/lg V) для разреженного графа?
Невозможно использовать очередь с минимальным приоритетом в случае плотного графа. Каким будет его влияние на временную сложность Дейкстры?

Ссылка-CLRS Страница-662 3-е изд.

Пожалуйста прочитано:

источник

2013-12-23 Sonali

Похоже, что они получают выражение 'E = o (V^2/lg V)' * прямо там, в указанной вами ссылке *. Вам нужны объяснения по поводу этого вывода, или я неправильно понял, что там написано? – anatolyg

Кроме того, в отношении вашего вопроса (2); ссылка, которую вы предоставляете, указывает на ее влияние как «O ((V + E) lg (V))», не так ли? – anatolyg

Предлагаю вам изменить название и заменить № по номеру. Нет, это еще одно слово, и в первый раз, когда я прочитал вопрос, я смутился. – fotanus

Substitute, что выражение для E в общее время, O((V + E)lg V), и вы увидите, что если E=o(V^2/lg V) общее будет o(V^2), что является улучшение за O(V^2) время работы без использования Minheap.
Снова замените. Предположим, что полный график, E = V^2. Затем время работы становится O((V + V^2)lg V) = O(V^2 lg V), что хуже O(V^2).

источник

2013-12-23 15:24:17

Число краев в разреженном графике?

ответ

Смежные вопросы