Ресурсы, которые я нашел по сложности времени, неясно, когда можно игнорировать термины в уравнении сложности времени, особенно с неполиномиальными примерами.
Для меня ясно, что при условии чего-то вида n 2 + n + 1 последние два члена не имеют значения.
В частности, с учетом двух категорий, 2 n и n * (2 n ), находится ли второй в том же порядке, что и первый? Имеет ли значение дополнительное n умножение? Обычно ресурсы просто говорят, что x n находится в экспоненциальной степени и растет намного быстрее ... затем двигаться дальше.
Я могу понять, почему это не так, поскольку 2 n будет значительно опережать n, но поскольку они не суммируются, это будет иметь большое значение при сравнении двух уравнений, фактически разница между ними всегда будет равна n, что кажется важным по меньшей мере.
n! = o((n+1)!)
то есть он асимптотически растет строго медленнее.Ответы:
Вам придется перейти к формальному определению большой O (
O
), чтобы ответить на этот вопрос.Определение таково, что
f(x)
принадлежитO(g(x))
тогда и только тогда, когда существует предел, т. Е. Не бесконечность. Короче говоря, это означает, что существует постоянная , такая, что значение никогда не бывает больше, чем .limsupx → ∞ (f(x)/g(x))
M
f(x)/g(x)
M
В случае вашего вопроса пусть и пусть . Тогда это будет расти бесконечно. Поэтому не принадлежит
f(n) = n ⋅ 2n
g(n) = 2n
f(n)/g(n)
n
f(n)
O(g(n))
.источник
O(f(x)/g(x))
; Уведомление big-O - это сокращение для набора функций, а не одной функции, значение которой вы можете ограничить. Тем не менее, я думаю, что это правда, что вы можете показать, чтоf(x) = O(g(x))
еслиlim(x->infinity) f(x)/g(x)
существует.lim sup
вместоlim
.x
, а не для всех значенийx
.Быстрый способ увидеть, что
n⋅2ⁿ
больше, - это изменить переменную. Пустьm = 2ⁿ
. Тогдаn⋅2ⁿ = ( log₂m )⋅m
(логарифмирование основанию 2 с обеих сторонm = 2ⁿ
даетn = log₂m
), и вы можете легко показать , чтоm log₂m
растет быстрееm
.источник
lg
? Логарифм в базе 2?lg
это обозначение ISO для логарифма base-10, а не использование без учета базы, наиболее часто используемое при обсуждении асимптотического времени выполнения. См en.wikipedia.org/wiki/Logarithm#Particular_basesЯ согласен, что
n⋅2ⁿ
это не такO(2ⁿ)
, но я подумал, что это должно быть более явным, так как ограничение верхнего уровня не всегда имеет место.По формальному определению Big-O:
f(n)
есть,O(g(n))
если существуют константыc > 0
иn₀ ≥ 0
такие, которые для всехn ≥ n₀
нас естьf(n) ≤ c⋅g(n)
. Легко показать, что таких констант не существует дляf(n) = n⋅2ⁿ
иg(n) = 2ⁿ
. Тем не менее, это может быть показано, чтоg(n)
вO(f(n))
.Другими словами,
n⋅2ⁿ
ограничен снизу2ⁿ
. Это интуитивно понятно. Хотя они оба экспоненциальны и, следовательно, одинаково маловероятны для использования в большинстве практических обстоятельств, мы не можем сказать, что они одного и того же порядка, потому что2ⁿ
обязательно растут медленнее, чемn⋅2ⁿ
.источник
f(n) = 2*2^n
Я думаю ты имел ввидуn*2^n
?Я не спорю с другими ответами, которые говорят, что
n⋅2ⁿ
растет быстрее, чем2ⁿ
. Ноn⋅2ⁿ
растет все еще только экспоненциально.Когда мы говорим об алгоритмах, мы часто говорим, что сложность времени растет экспоненциально. Таким образом, мы считаем
2ⁿ
,3ⁿ
,eⁿ
,2.000001ⁿ
, или нашn⋅2ⁿ
в такой же группе сложности с экспоненциальным растет.Чтобы придать ему немного математического смысла, мы считаем, что функция
f(x)
растет (не быстрее) экспоненциально, если существует такая постояннаяc > 1
, что .f(x) = O(cx)
Для
n⋅2ⁿ
константыc
может быть любое число больше, чем2
, давайте возьмем3
. Затем:n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿ
и это меньше, чем1
для любогоn
.Так что
2ⁿ
растет медленнее, чемn⋅2ⁿ
последний, в свою очередь, растет медленнее, чем2.000001ⁿ
. Но все три из них растут в геометрической прогрессии.источник
Вы спросили: "Является ли второе в том же порядке, что и первое? Имеет ли значение дополнительное n умножение?" Это два разных вопроса с двумя разными ответами.
n 2 ^ n растет асимптотически быстрее, чем 2 ^ n. Вот на этот вопрос ответили.
Но вы могли бы спросить: «Если алгоритм A занимает 2 ^ n наносекунд, а алгоритм B - n 2 ^ n наносекунд, какой самый большой n, где я могу найти решение за секунду / минуту / час / день / месяц / год? ответы: n = 29/35/41/46/51/54 против 25/30/36/40/45/49. На практике нет большой разницы.
Размер самой большой проблемы, которая может быть решена за время T, составляет O (ln T) в обоих случаях.
источник