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

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

terminology asymptotics mathematical-analysis landau-notation Фрэнк
источник

может быть,

m

$m$ зависит от

n

$n$

Андрей

Ответы:

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

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

\frac{1}{2} (m + n) \leq max {m, n} \leq m + n \leq 2 max {m, n},

$\frac{1}{2}(m+n) \le \max\{m,n\} \le m+n \le 2 \max\{m,n\},$ вы можете сделать вывод, что

O (n + m)

$O(n+m)$ и

O (max {m, n})

$O(\max\{m,n\})$ являются эквивалентными асимптотическими верхними оценками.

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

O (2^{m} + m) = O (2^{m}) ⊋ O (m) = O (min {2^{m}, m}) .

$O(2^m+m)=O(2^m) \supsetneq O(m)=O(\min\{2^m,m\}).$

A.Schulz
источник

Я думаю, что примечательно, что они пишут в аннотации: «Мы показываем, что невозможно определить нотацию big-O для функций более чем одной переменной способом, который подразумевает свойства, обычно используемые в анализе алгоритма. Мы также демонстрируем, что общие определения не подразумевайте эти свойства, даже если функции в нотации big-O ограничены тем, чтобы быть строго неубывающими ".

Рафаэль

В качестве продолжения моего комментария, приведенного выше, недавняя статья . Общее определение O-нотации для алгоритмического анализа, выполненное К. Рутаненом (2015) , показывает, как определить осмысленную O-нотацию для общих множеств, включая .

N^{2}

$\mathbb{N}^2$

Рафаэль

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

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

Кристоффер Арнсфельт Хансен
источник

Ссылка в моем ответе ссылается на статью Хауэлла, которая действительно является хорошим ответом на этот вопрос.

А.Шульц

@ A.Schulz: Действительно, я печатал свой ответ одновременно с вами.

Кристоффер Арнсфельт Хансен

Я сторонник того, чтобы быть осторожным с условиями Ландау, поэтому я согласен, но это содержит слишком много разглагольствования для хорошего ответа.

Рафаэль

@ Рафаэль: Ответ не подразумевается как напыщенная речь, но, возможно, его можно было бы сформулировать более точно. Дело в том, что вопрос в основном, что означает большой О с более чем одним параметром. Ответ заключается в том, что это должно означать, что существует единство мнений в сообществе алгоритмов, чему учат на курсах по алгоритмам и т. Д. Я хочу сказать, что, похоже, нет такого консенсуса относительно того, что именно означает нотация.

Кристоффер Арнсфельт Хансен