Количество ребер в разреженном графе?

Я читал Алгоритм Дейкстры в гл. 24 и запутался со значением разреженного графа. Они говорят: «Если граф достаточно разреженный — в частности, E= o(V^2/lg V) — мы можем улучшить алгоритм, реализовав очередь с минимальным приоритетом с двоичной минимальной кучей».

Мои вопросы

  1. Откуда они взяли выражение E= o(V^2/lg V)для разреженного графа?

  2. Можем ли мы использовать очередь с минимальным приоритетом в случае плотного графа. Как это повлияет на временную сложность Дейкстры?

Ссылка-CLRS Page-662 3-е изд.

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


algorithm dijkstra
person Sonali    schedule 23.12.2013    source источник
comment
Кажется, они выводят выражение E = o(V^2/lg V) прямо в предоставленной вами ссылке. Вы хотите пояснений по этому выводу, или я неправильно понял, что там написано?   -  person anatolyg    schedule 23.12.2013
comment
Кроме того, по вашему вопросу (2); ссылка, которую вы предоставляете, указывает на ее эффект как O((V+E)lg(V)), не так ли?   -  person anatolyg    schedule 23.12.2013
comment
Я предлагаю вам отредактировать заголовок и заменить номер на номер. Нет — это другое слово, и когда я впервые прочитал вопрос, я был сбит с толку.   -  person fotanus    schedule 23.12.2013
comment
@anatolyg ты неправильно понял   -  person Sonali    schedule 24.12.2013

Ответы (1)


arrow_upward
2
arrow_downward

  1. Подставьте это выражение для E в общее время выполнения, O((V + E)lg V), и вы увидите, что если E=o(V^2/lg V), общее время будет o(V^2), что является улучшением по сравнению с O(V^2) временем выполнения без использования minheap.

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

person Imre Kerr    schedule 23.12.2013