Big O Обозначение выражения

Question

Если у меня есть алгоритм, для выполнения которого требуется 4n^2 + 7n ходов, каково его значение O?О(4n^2)?О(п^2)?

Я знаю, что 7n обрезается, но не знаю, стоит ли мне сохранять коэффициент n^2 или нет.

Спасибо

Answer 1

Вам следует отбросить любые коэффициенты, потому что вопрос на самом деле задается «по порядку», который пытается охарактеризовать его как линейный, экспоненциальный, логарифмический и т. д.То есть, когда n очень велико, коэффициент не имеет большого значения.

Это также объясняет, почему вы опускаете +7n, потому что, когда n очень велико, этот член имеет относительно малое значение для окончательного ответа.Если вы знакомы с исчислением, вы можете сказать lim n->inf(4*n^2+7n) ~= lim n->inf(4*n^2) ~= lim n->inf(n^2)

Вы также можете подумать об этом в графическом смысле...то есть, если вы построите график функции 4n^2 + 7n для все больших и больших значений n, математик может сказать: «Это похоже на n^2».Конечно, это должен быть довольно либеральный математик, поскольку это не строгое утверждение, но именно это и пытается передать O(...).

Answer 2

Коэффициенты не имеют значения в нотации Big O, так что это просто O(n²). Как объясняет Википедия:

[...] коэффициенты становятся нерелевантными, если мы сравниваем их с любым другим порядком выражения, например с выражением, содержащим термин n³ или н².

Answer 3

Каждый, кто читает или пишет о сложности алгоритмов, должен точно знать, что Символы Ландау и асимптотические обозначения есть, иначе они не очень понимают, что происходит, или просто имеют приблизительное (и часто вводящее в заблуждение) представление.

Чтобы упростить (значительно), позвольте f и g быть две функции f : N -> N и g : N -> N.Мы говорим, что f is O(g) тогда и только тогда, когда существует константа M > 0 такой, что |f(n)| < M|g(n)|, для всех n > M.То есть, более неформально, начиная с большого значения n, все значения f(n) меньше, чем кратное g(n) (т.е. g растет быстрее чем f).

Это определение эквивалентно

f is O(g) <==> There is K >= 0 such that lim{n -> +oo} |f(n)|/|g(n)| = K

Итак, давайте возьмем f(n) = 4n^2 + 7n и g(n) = n^2, и попытайтесь доказать f is O(g) (я опущу {n -> +oo}):

lim |f(n)|/|g(n)| = lim f(n)/g(n) = lim (4n^2 + 7n) / n^2 = 4 + lim 7n/n^2 =
                  = 4 + lim 7/n = 4 + 0 = 4

Это подразумевает, что существует M такой, что n > M ==> |f(n)| < M|g(n)|, и поэтому f is O(g).

Так что технически правильно сказать 4n^2 + 7n is O(4n^2), как правильно сказать 4n^2 + 7n is O(n^3), 4n^2 + 7n is O(e^n), и так далее.Но чтобы иметь смысл, нас интересует нижняя граница.Так что если f is O(e^n) и f is O(n^2), нам больше интересно знать, что f is O(n^2), поскольку это гораздо более ограничительно.

ОЧЕНЬ ВАЖНОЕ замечание

Чрезвычайно важно при выборе алгоритма понимать, что обозначения «большое О» относится к асимптотические случаи, то есть, если вы считаете чрезвычайно, невообразимые огромные затраты, что может значительно превосходить вычислительные мощности, доступные в известной вселенной (т. е. бесконечные входные наборы, математически выраженные формулой {n -> +oo}).

Для практического использования (т.е. не так огромные входные данные), при выборе алгоритма вы, конечно, увидите алгоритмы-кандидаты обозначения «большое О», но вы должны быть уверены, что выбранный алгоритм хорошо адаптирован (и работает лучше) для ваших (ожидаемых) входных данных.

Наконец, обычно более эффективные алгоритмы сложнее понять и правильно реализовать.Этот факт также необходимо учитывать при выборе алгоритма (т. е. это время, которое я потрачу отладка и исправление моей реализации этого алгоритма значительно превосходит время, которое мне пришлось бы ждать с другим алгоритмом, с худшим обозначением большого О?.Если да, то вам следует рассмотреть более простой и менее эффективный алгоритм, поскольку общее решение будет более эффективным).

Answer 4

Это O(n^2).Постоянные факторы «переходят в О».Вы сохраняете только самый большой показатель, поскольку он является доминирующим.И вы можете опустить коэффициенты, поскольку при сравнении разных алгоритмов даже очень большие коэффициенты дают меньшие общие числа, чем больший показатель степени (при достаточно большом n).

Answer 5

Заявление типа

4n² + 7n = O(n²)

означает, что для некоторого постоянного множителя c, выражение cn² в конце концов обгонит 4n² + 7n.Технически нет ничего плохого в том, чтобы оставить здесь коэффициент — O(n²) и O(4n²) означают то же самое, потому что любая константа c ибо первое можно заменить на c/4 для последнего.Однако такая вещь менее ясна, возможно, вводит в заблуждение и определенно нестандартна.

Answer 6

Математически говоря, вы должны написать O(4n²).Это означает, что функция сложности ваших алгоритмов ведет себя как n->4n² в направлении положительной бесконечности.

Но в информатике/алгоритме вы должны написать только O(n²), чего достаточно для категоризации вашего алгоритма.