Это может быть наивный вопрос, но я новичок в концепции нотации и сложности Big-O и не нашел ответа на это. Я имею дело с проблемой, для которой алгоритм (2n + 1)! время проверяет состояние. Могу ли я сказать, что сложность проблемы O (n!) Или сложность O ((2n + 1)!)?Являются ли две сложности O ((2n + 1)!) И O (n!) Равными?
Использование Stirling's approximation:
n! ~ (n/e)^n * sqrt(2 * pi * n)
Тогда
(2n + 1)! ~ ((2n + 1)/e)^(2n + 1) * sqrt(2 * pi * (2n + 1))
>= (2n/e)^(2n) * sqrt(2 * pi * 2n)
= 2^2n * (n/e)^(2n) * sqrt(2) * sqrt(2 * pi * n)
= sqrt(2) * (2^n)^2 * ((n/e)^n)^2 * sqrt(2 * pi * n)
И теперь это довольно понятно, почему нет никакой надежды O((2n + 1)!) быть O(n!): экспоненциальные факторы гораздо хуже. Это больше похоже на O((2n + 1)!)O((n!)^2).
Вот определение: https://en.wikipedia.org/wiki/Big_O_notation. Таким образом, нам нужно проверить, существует ли такая константа с и n0, что:
(2n+1)! < cn! for n > n0
Наглядно от наблюдения, как (2n + 1)! и н! себя:
http://www.wolframalpha.com/input/?i=n!+%3E%282n+%2B1%29!
(2n + 1)! просто идет в два раза быстрее, поэтому независимо от «c» он всегда будет достигать n !. Поэтому вы не можете упростить n !.
Вам нужно посмотреть (2n + 1)!/N !. Просто сравнивая это, можно было бы верить, что n = o (3n). – Teepeemm
Ну, но действительно O (3n) = O (n). – BartoszKP
Я согласен, но если я изменю свой метод, чтобы изучить http://www.wolframalpha.com/input/?i=3n+%3E+n, в противном случае меня могут привести к заключению. – Teepeemm
(2n + 1)! = n! (n + 1) ... (2n + 1)
O ((2n + 1)!) = O (n!) O ((n + 1) ... (2n + 1))
==>
O (1) = о ((п + 1) ... (2n + 1))
O (п!) = о ((2n + 1)!)
@icepack с вашим оправданием можно заключить, например, O (2n + 1) больше O (n), однако, как я знаю, O (2n + 1) = O (n). – Barpa
@ Барпа Нет, это не так. Это мало-о в последних двух строках с правой стороны. – SomeWittyUsername
'=' не имеет смысла в последних двух строках. Вы имеете в виду '⊂'. – Teepeemm
Пусть (N, c) - любая упорядоченная пара положительных постоянных. Пусть n - любое целое число такое, что n> N и n> c.
Затем (2n + 1)! > (2n + 1) * n! > cn!
Таким образом, для любой пары положительных постоянных (N, c) существует n> N такое, что (2n + 1)! > cn !, так что (2n + 1)! не является O (n!).
O ((2n + 1)!) Содержит функцию (2n + 1) !, которая не входит в O (n!), Поэтому O ((2n + 1)!) И O (n!) не то же самое.
(Я согласен с желанием LaTeX.)
Это вопрос домашней работы, не так ли? – mor
Нет, это часть моей дипломной работы. – Barpa