Что это значит, когда мы говорим, что временная сложность равна O(M+N)?

Это то же самое, что сказать

O(max(M,N))?

Я изучаю временную сложность, и этот тип сложности появляется снова и снова с графиками. Я не совсем понимаю, что они имеют в виду под

O(M+N),

где M=количество ребер N=количество вершин.


graph algorithm asymptotic-complexity
person Aravind    schedule 23.06.2013    source источник
comment
Вместо того, чтобы задавать этот вопрос, попробуйте доказать его истинность, используя определения. Если вы не можете этого сделать, попробуйте доказать, что это ложь. Если ничего не помогает, вы можете опубликовать свои попытки здесь или на другом форуме (возможно, обмен стеками информатики или обмен стеками математики?). Но я думаю, что если вы просто посмотрите на определение Big-Oh, вы обнаружите, что оно верно довольно быстро (ну, после того, как вы получите базовое понимание строгого определения).   -  person rliu    schedule 23.06.2013
comment
Кроме того, причина, по которой они склонны говорить O(M+N), заключается в том, что это более тесная граница, а также более четкая. Обычно это означает, что мы обрабатываем ребра и вершины в течение линейного времени, в то время как O(M) создаст впечатление, что, возможно, алгоритм полностью игнорирует вершины. Это также помогает, потому что реализация графового алгоритма часто значительно различается по производительности. Если ваш график разреженный (т. е. |M| очень мал), то вас может не волновать наличие фактора O(M^2 * ...) во временной сложности (т. е. вы бы предпочли O(M^2 * logN) вместо O(M*N), несмотря на то, что первый асимптотически медленнее).   -  person rliu    schedule 23.06.2013

Ответы (2)


arrow_upward
6
arrow_downward

O(M+N) совпадает с O(max(M,N))?

Да, это то же самое. Не теряя общности, можно сказать, что M >= N. Следовательно, O(max(M,N)) совпадает с O(M). В то же время M < M+N < M+M, поэтому O(M+N) совпадает с O(2*M), который, в свою очередь, совпадает с O(M).

person Sergey Kalinichenko    schedule 23.06.2013
comment
Не теряя общности? Я бы сказал, что вы говорите о верхней границе. Что делать, если граф разреженный? - person TheEmeritus; 23.06.2013
comment
@TheEmeritus Это не имеет значения: из двух чисел M и N одно будет больше, а другое меньше, или они будут равны. Если тот, который вы изначально обозначили как N, окажется больше, вы можете переименовать его как M. - person Sergey Kalinichenko; 23.06.2013
comment
@TheEmeritus Чтобы продолжить ответ dasblinkenlight, он имеет в виду следующее: en.wikipedia.org/wiki/Without_loss_of_generality< /а>. Это означает, что в других случаях доказательство остается тем же самым (часто потому, что вы можете просто переименовать переменную, как мы видим здесь). На самом деле мне не очень нравится это доказательство, так как оно на самом деле не относится к определению Большого-О и зависит от транзитивности Большого-О, когда это на самом деле не нужно (т.е. оно кажется мне окольным). Но для случайных целей я думаю, что это достаточно ясно - person rliu; 23.06.2013
comment
Что, если бы у нас был граф с десятью миллионами вершин и без ребер? - person Aravind; 23.06.2013
comment
@Aravind Тогда max(E,V) будет 10,000,000, а E+V также будет 10,000,000. Суть моего доказательства в том, что E+V не может превышать 2*max(E,V), следовательно, O(E+V) == O(max(E,V)). - person Sergey Kalinichenko; 23.06.2013

arrow_upward
1
arrow_downward

Предполагая, что у вас есть N вершин, количество ребер может варьироваться (от 0 до N^2, если это ориентированный граф, и от 0 до (N^2)/2 в противном случае). Вот почему при ответе у вас также есть N и M. Конечно, вы можете сказать, что O(M+N) = O(max(M,N)), но небрежно сказать, что это O(M+N).

person TheEmeritus    schedule 23.06.2013