Что считается асимптотическим улучшением для графовых алгоритмов?

Question

Допустим, мы пытаемся решить какую-то алгоритмическую задачу $A$ это зависит от входного размера $n$.Мы говорим алгоритм $B$ это происходит во времени $T(n)$, асимптотически лучше алгоритма $C$ который выполняется во времени $G(n)$ если у нас есть:$G(n) = O(T(n))$, но $T(n)$ это не так $O(G(n))$.

Мой вопрос связан с асимптотическим временем выполнения графовых алгоритмов, которое обычно зависит от $|V|$ и $|E|$.В частности, я хочу сосредоточиться на алгоритме Прима.Если мы реализуем приоритетную очередь с двоичной кучей, время выполнения будет $O(E\log V)$.С помощью кучи Фибоначчи мы могли бы получить время выполнения $O(V\log V + E)$.

Мой вопрос в том, говорим ли мы это $O(V\log V + E)$ асимптотически лучше, чем $O(E\log V)$?

Позвольте мне уточнить:Я знаю, что если график плотный, то ответ будет утвердительным.Но если $E=O(V)$ оба решения одинаковы.Меня больше интересует то, что обычно определенный в качестве асимптотического улучшения в этом случае мы имеем более одной переменной, и что еще хуже - переменные не являются независимыми ($V-1\le E, поскольку мы предполагаем, что граф связан для алгоритма Прима).

Спасибо!

Answer 1

Наиболее допустимое определение заключается в следующем.

Предположим , что $f(V,E),g(V,E)$ это два времени выполнения графовых алгоритмов, решающих одну и ту же задачу.

Мы говорим, что $f$ является асимптотическое улучшение в некотором режиме вкл . $g$ если существует последовательность $V_n,E_n$ с $V_n o \infty$ такой , что $$ \lim_{от n до infty} \frac{f(V_n,E_n)}{g(V_n, E_n)} = 0.$$

Иногда режим считается неинтересным, но это более субъективный вопрос.

Обратите также внимание, что проблема уже проявляется для функций с одной переменной.Рассмотреть $$ f(n) = n^2, \qquad g(n) = \begin{случаи} 2^n & ext{если } n = 2^m, \\ n & ext{в противном случае}.\конец{случаи} $$ Является $f$ асимптотическое улучшение по сравнению $g$?Это предназначено для входных данных определенной длины, и это действительно так в соответствии с нашим разрешающим определением выше.