Большая Нотация O выражения
Если у меня есть алгоритм, который берет 4n^2 + 7n, перемещается для выполнения, каков его O? O (4n^2)? O (n^2)?
Я знаю, что 7n отключен, но я не знаю, должен ли я сохранить n^2 коэффициент или нет.
Спасибо
6 ответов
Вы должны отбросить любые коэффициенты, потому что вопрос действительно просят «по порядку», который пытается охарактеризовать его как линейным, экспоненциальным, логарифмическим и т. Д. ... Когда 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 (...) пытается передать.
Коэффициенты не имеют отношения к большому обозначению, поэтому это просто o (n 2 ). Как объясняет Википедию :
[...] Коэффициенты становятся неактуальными, если мы сравним с любым другим порядком выражения, такого как выражение, содержащее срок N 3 или N 2 .
Это o (n ^ 2). Постоянные факторы «переезжают в о». Вы держите только самый большой показатель, поскольку это единственное доминирование. И вы можете оставить коэффициенты с тех пор, когда при сравнении различных алгоритмов даже очень большие коэффициенты приводят к меньшим общем числам, чем иметь более широкий показатель (при достаточно большом количестве).
Математически говоря, вы бы написали о (4N²). Это означает, что функция сложности ваших алгоритмов ведет себя как N-> 4n² к положительной бесконечности.
Но в компьютерной науке / алгоритме вы бы написали только O (N²), что достаточно для классификации вашего алгоритма.
Все чтение или пишут о сложности алгоритмов, должны точно знать, что такое символы Ландау и асимптотических обозначений , в противном случае они не понимают, что продолжается или просто есть приблизительную (и часто вводящее в заблуждение) идею.
Чтобы упростить (много), пусть f и G - две функции f: n -> n и G: n -> N . Мы говорим, что f ì o (g) , если и только если есть постоянная m> 0 такое, что | f (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 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) | f o (g) .
Так что технически правильно сказать 4n ^ 2 + 7n - o (4n ^ 2) , так как правильно сказать 4n ^ 2 + 7n - o (n ^ 3) , 4n ^ 2 + 7n - O (E ^ n) , и так далее. Но быть значимым, мы заинтересованы в нижней границе. Таким образом, если f ì o (e ^ n) и f ì o (n ^ 2) , мы более заинтересованы в том, чтобы знать, что f o (n ^ 2) , так как это гораздо более ограничительно.
Очень важное примечание
Что крайне очень важно при выборе алгоритма, состоит в том, чтобы понять, что нотации Big-o относится к асимптотическим случаям , то есть при рассмотрении Чрезвычайно невообразимые огромные входы , которые могут выходить за пределы вычислительной мощности, доступной в известной вселенной (т. Е., IE, бесконечные входные наборы, выраженные математически с помощью {n -> + oo} ).
Для практического использования (например, не так Огромные входы), при выборе алгоритма, конечно, вы соблюдаете алгоритмы кандидата нотации Big-O , но вы должны быть уверены, что Выбранный алгоритм хорошо адаптирован (и лучше выполняет) для вашего (ожидаемого) ввода.
Наконец, обычно лучше проводить алгоритмы, сложнее понять и реализовать должным образом. Вы должны рассмотреть этот факт, а также при выборе алгоритма (т. Е. - это время, которое я потрачу отладка и фиксирование моей реализации этого алгоритма, значительно превосходящего времени, когда мне придется ждать с другим алгоритмом , с худшим нотацией Big-o? . Если это так, вы должны рассмотреть более простой, менее эффективный алгоритм, так как общее решение будет более эффективно).
Утверждение, как
4n² + 7n = O(n²)
означает, что для некоторого постоянного множителя C , выражение CN² , в конечном итоге повернут 4N² + 7N . Технически не неверно покидать коэффициент там, - o (n²) и o (4n²) означает то же самое, потому что любая постоянная C для Бывший может быть заменен C / 4 для последнего. Однако такая вещь менее четкая, возможно вводящая в заблуждение и определенно нестандартное.