Что означает ?

44

Это основной вопрос, но я думаю, что совпадает с , поскольку больший член должен доминировать при переходе к бесконечности? Кроме того, это будет отличаться от O (\ min (m, n)) . Это правильно? Я продолжаю видеть это обозначение, особенно при обсуждении алгоритмов графа. Например, вы обычно видите: O (| V | + | E |) (например, смотрите здесь ).O(m+n)O(max(m,n))O(min(m,n))O(|V|+|E|)

Фрэнк
источник
может быть, m зависит от n
Андрей

Ответы:

33

Вы правы. Обратите внимание, что термин O(n+m) слегка нарушает классическую нотацию big-O , которая определена для функций в одной переменной. Однако есть естественное расширение для нескольких переменных.

Проще говоря, так как

12(m+n)max{m,n}m+n2max{m,n},
вы можете сделать вывод, что O(n+m) и O(max{m,n}) являются эквивалентными асимптотическими верхними оценками.

С другой стороны, O(n+m) отличается от O(min{n,m}) , поскольку, если вы установите n=2m , вы получите

O(2m+m)=O(2m)O(m)=O(min{2m,m}).
A.Schulz
источник
3
Я думаю, что примечательно, что они пишут в аннотации: «Мы показываем, что невозможно определить нотацию big-O для функций более чем одной переменной способом, который подразумевает свойства, обычно используемые в анализе алгоритма. Мы также демонстрируем, что общие определения не подразумевайте эти свойства, даже если функции в нотации big-O ограничены тем, чтобы быть строго неубывающими ".
Рафаэль
4
В качестве продолжения моего комментария, приведенного выше, недавняя статья . Общее определение O-нотации для алгоритмического анализа, выполненное К. Рутаненом (2015) , показывает, как определить осмысленную O-нотацию для общих множеств, включая . N2
Рафаэль
25

Хотите верьте, хотите нет, но (по моему опыту) кажется, что многие алгоритмы на самом деле не задумывались о том, что формально означает большая буква O, и когда вас об этом спрашивают, вы можете получить несколько разных ответов. Некоторые вопросы обсуждаются в статье Родни Р. Хауэлла « Об асимптотической записи с множественными переменными ».

Любопытно, что также кажется, что большинство вводных курсов по алгоритмам тратят много времени на то, чтобы быть очень формальными в отношении больших O-нотаций с одной переменной, а затем в следующие недели с радостью используют нотацию для графовых алгоритмов с несколькими переменными случайным образом, не обсуждая, что запись на самом деле означает.

Кристоффер Арнсфельт Хансен
источник
Ссылка в моем ответе ссылается на статью Хауэлла, которая действительно является хорошим ответом на этот вопрос.
А.Шульц
1
@ A.Schulz: Действительно, я печатал свой ответ одновременно с вами.
Кристоффер Арнсфельт Хансен
1
Я сторонник того, чтобы быть осторожным с условиями Ландау, поэтому я согласен, но это содержит слишком много разглагольствования для хорошего ответа.
Рафаэль
4
@ Рафаэль: Ответ не подразумевается как напыщенная речь, но, возможно, его можно было бы сформулировать более точно. Дело в том, что вопрос в основном, что означает большой О с более чем одним параметром. Ответ заключается в том, что это должно означать, что существует единство мнений в сообществе алгоритмов, чему учат на курсах по алгоритмам и т. Д. Я хочу сказать, что, похоже, нет такого консенсуса относительно того, что именно означает нотация.
Кристоффер Арнсфельт Хансен