Будет (7n) !, (5n / 16)!и н!все быть Θ (n!)?
Я думаю, что есть два ответа на ваш вопрос.
Короче, с чисто теоретической точки зрения.Из этих 3 только n! относится к классу Θ(n!).Второе лежит в O(n!) (обратите внимание, что big-O вместо big-Theta), а (7n)! медленнее, чем Θ(n!), оно лежит в Θ((7n)!)
Существует также более длинный, но более практичныйответ.И чтобы добраться до него, мы сначала должны понять, что в этом такого важного для всего бизнеса Биг-О и Биг-Тета?
Дело в том, что для многих практических задач существует множество алгоритмов, и не все они одинаково или даже одинаково эффективны.Таким образом, практический вопрос заключается в следующем: можем ли мы как-то уловить эту разницу в производительности простым для понимания и сравнения способом?И это проблема, которую пытаются решить big-O / big-Theta.Идея этого метода заключается в том, что если мы посмотрим на некоторый алгоритм с какой-то сложной реальной формулой для точного времени, то есть только один член, который растет быстрее, чем все остальные, и, таким образом, доминирует во времени, когда проблема становится больше.Итак, давайте сжимаем эту большую формулу в этот доминирующий термин.Затем мы можем сравнить эти термины и, если они отличаются, мы можем легко сказать, какой алгоритм лучше (7*n^2 явно лучше, чем 2*n^3).
Другая идея состоит в том, что термин «операция»обычно не так хорошо определено на уровне, который люди обычно думают об алгоритмах.Какая «операция» на самом деле отображается на одну инструкцию процессора, а какая на несколько, зависит от многих факторов, таких как конкретное оборудование.Кроме того, сами инструкции могут выполняться по-разному.Более того, иногда время работы алгоритма зависит от доступа к памяти, а не от инструкций ЦП, и эти компоненты нелегко аддитивны.Мораль этой истории состоит в том, что если два алгоритма отличаются только по скалярному коэффициенту, вы не можете сравнить эти алгоритмы только теоретически.Вам нужно сравнить некоторые реализации в определенной среде.Вот почему мера сложности алгоритмов обычно сводится к чему-то вроде O(n^k), где k - это константа.
Существует еще одно соображение: практичность.Если алгоритм является некоторым полиномом, существует огромная практическая разница между случаями a=3 и a=4 в O(n^a).Но если это что-то вроде O(2^(n^a)), то нет большой разницы, что такое a и a>1.Это потому, что 2^n растет достаточно быстро, чтобы сделать его практически непрактичным практически для любого реалистичного n независимо от a.Таким образом, на практике это довольно подходящее приближение, чтобы поместить все такие алгоритмы в одну корзину «экспоненциальных алгоритмов» и сказать, что все они непрактичны, даже несмотря на то, что между ними существует огромная разница.Вот откуда берутся некоторые математически нетрадиционные обозначения, такие как 2^O(n).
С этой последней практической точки зрения разница между Θ(n!) и Θ((7n)!) также очень мала: оба абсолютно непрактичны, потому что оба лежат за пределами дажеэкспоненциальный интервал 2^O(n) (см. формула Стирлинга , которая показывает, что n! растет немного быстрее, чем (n/e)^n).Поэтому имеет смысл поместить все такие алгоритмы в другую группу «факторной сложности» и пометить их как непрактичные.