Являются ли 2 ^ n и n * 2 ^ n одинаковыми по сложности?

178

Ресурсы, которые я нашел по сложности времени, неясно, когда можно игнорировать термины в уравнении сложности времени, особенно с неполиномиальными примерами.

Для меня ясно, что при условии чего-то вида n 2 + n + 1 последние два члена не имеют значения.

В частности, с учетом двух категорий, 2 n и n * (2 n ), находится ли второй в том же порядке, что и первый? Имеет ли значение дополнительное n умножение? Обычно ресурсы просто говорят, что x n находится в экспоненциальной степени и растет намного быстрее ... затем двигаться дальше.

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

Мэтти-д
источник
8
По моему мнению, учитывая, что NLogN считается строго медленнее, чем N, но большинству людей на самом деле все равно, насколько, можно с уверенностью сказать, что N2 ^ N просто медленнее, чем 2 ^ N, но не "достаточно медленнее" для людей. заботиться ..
Джек,
@tobias_k, я понимаю этот момент, но рассмотрим пример O (n!). Будет ли дополнительный n термин действительно другим? O (n!) - к O (n * n!), Как O (n!) - к O ((n + 1)!), То есть тот же граф просто сдвинут. Рост такой же, хотя ... В этом случае, несмотря на то, что он строго большой, отличается ли рост? Разве это не то, что время заботится о сложности?
matty-d
3
@JackWu, но большинству людей на самом деле все равно, сколько вам придется сортировать сотни миллионов записей с помощью nlogn вместо n :)
CB
4
Фактически, n! = o((n+1)!)то есть он асимптотически растет строго медленнее.
chepner
16
Обратите внимание, что это не имеет ничего общего с теорией сложности, это «просто» об асимптотике. Кроме того, такого рода вопросы, вероятно, лучше для компьютерных наук .
Рафаэль

Ответы:

231

Вам придется перейти к формальному определению большой O ( O), чтобы ответить на этот вопрос.

Определение таково, что f(x) принадлежит O(g(x))тогда и только тогда, когда существует предел, т. Е. Не бесконечность. Короче говоря, это означает, что существует постоянная , такая, что значение никогда не бывает больше, чем .limsupx → ∞ (f(x)/g(x))Mf(x)/g(x)M

В случае вашего вопроса пусть и пусть . Тогда это будет расти бесконечно. Поэтому не принадлежитf(n) = n ⋅ 2ng(n) = 2nf(n)/g(n)nf(n)O(g(n)) .

Ивайло Странджев
источник
5
Чуть проще прочитать определение, см. Здесь
Alden
3
Формально говоря, вы не можете взять предел O(f(x)/g(x)); Уведомление big-O - это сокращение для набора функций, а не одной функции, значение которой вы можете ограничить. Тем не менее, я думаю, что это правда, что вы можете показать, что f(x) = O(g(x))если lim(x->infinity) f(x)/g(x)существует.
chepner
44
Предел не должен существовать; отношение должно быть ограничено только константой для достаточно большого x. Например, 2 + sin (x) находится в O (1), но (2 + sin (x)) / 1 не приближается к пределу при x-> бесконечности.
user2357112 поддерживает Monica
2
Определение будет правильным с lim supвместо lim.
Дэвид Эйзенстат
11
@IvayloStrandjev, пожалуйста, обратите внимание, что ваше краткое описание неверно. Это должно быть верно для достаточно большого x, а не для всех значений x.
К.Стефф
85

Быстрый способ увидеть, что n⋅2ⁿбольше, - это изменить переменную. Пусть m = 2ⁿ. Тогда n⋅2ⁿ = ( log₂m )⋅m(логарифмирование основанию 2 с обеих сторон m = 2ⁿдает n = log₂m), и вы можете легко показать , что m log₂mрастет быстрее m.

chepner
источник
3
Спасибо! Это лучший ответ на мой взгляд. Доказательства, основанные на формальных определениях, верны, но если у вас есть какой-то камень преткновения, очень удобная и знакомая аналогия сделает работу лучше и быстрее.
Джон П
1
Глупый вопрос, что это lg? Логарифм в базе 2?
Пьер Арло,
3
Это ленивое сокращение. В информатике это означает «основание 2», потому что в основном это результат стратегий «разделяй и властвуй». В нотации big-O он может представлять что угодно, поскольку логарифм base-x числа отличается от его логарифма base-y только на постоянный коэффициент, независимо от x и y.
chepner
3
Я должен отметить в ретроспективе, что lgэто обозначение ISO для логарифма base-10, а не использование без учета базы, наиболее часто используемое при обсуждении асимптотического времени выполнения. См en.wikipedia.org/wiki/Logarithm#Particular_bases
chepner
Хорошо, конечно, но я не понимаю, почему более очевидно, что m log m растет быстрее, чем m, чем n 2 ^ n растет быстрее, чем 2 ^ n.
Джечлин
10

Я согласен, что 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ⁿ.

ZPR
источник
f(n) = 2*2^nЯ думаю ты имел ввиду n*2^n?
tobias_k
4

Я не спорю с другими ответами, которые говорят, что 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 * 2 ^ n больше 2,000001 ^ n до n = 34 726 000. В этот момент 2 ^ n - это число с более чем 10 миллионами цифр, так что это не имеет
большого
1
@ gnasher729 Это просто константа, которую мы можем опустить, так как f (n) и c * f (n) имеют одинаковую сложность с точки зрения big-O. например, 40'000'000 * 2.000001 ^ n больше, чем n * 2 ^ n сразу. Но вы правы, это не имеет большого значения, я бы сказал, что это не имеет большого значения, как только мы достигаем экспоненциального роста (если только мы не получим только небольшие значения n).
Андрей
2

Вы спросили: "Является ли второе в том же порядке, что и первое? Имеет ли значение дополнительное 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) в обоих случаях.

gnasher729
источник