Каждый, кто читает или пишет о сложности алгоритмов, должен точно знать, что представляют собой символы Ландау и асимптотические обозначения , в противном случае они на самом деле не понимают, что происходит, или просто имеют приблизительная (и часто вводящая в заблуждение) идея.
Чтобы упростить (много), пусть 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), так как это намного более ограничительно.
ОЧЕНЬ ВАЖНОЕ примечание
Чрезвычайно важно при выборе алгоритма понимать, что нотации big-O относятся к асимптотическим случаям , то есть, когда вы рассматриваете чрезвычайно, невообразимые огромные входные данные , что может выходить далеко за пределы вычислительной мощности, доступной в известной вселенной (т. Е. Бесконечных входных множеств, математически выраженных {n -> +oo}).
Для практического использования (т. Е. Не , поэтому огромные входные данные), при выборе алгоритма, конечно, вы будете соблюдать алгоритмы-кандидаты big-O нотации , но вы должны быть уверены, что выбранный алгоритм хорошо адаптирован (и работает лучше) для вашего (ожидаемого) ввода.
Наконец, обычно более эффективные алгоритмы труднее понять и правильно реализовать. Вы также должны учитывать этот факт при выборе алгоритма (т. Е. - это время, которое я потрачу на отладку и исправление моей реализации этого алгоритма, значительно превосходящее время, которое мне пришлось бы ждать с другим алгоритмом , с худшей нотацией big-O? . Если это так, вы должны рассмотреть более простой, менее эффективный алгоритм, поскольку общее решение будет более эффективным).