Является ли O (N! * N) приемлемым классом большой сложности, или я убираю константу и просто говорю O (N!)?

Question

Является ли O (N! N) приемлемым классом большой сложности, или мне удалить константу и просто сказать O (N!)?

Answer 1

См. Что такое O (log (n!)) И O (n!) И аппроксимация Стирлинга , в которой обсуждается связь между O(n!) и O(n^n). Это должно помочь вам определить подходящий big-O при умножении их на n.

Дополнительный n в вашей задаче не является константой и не доминирует n!, поэтому он не исчезает из функции при преобразовании из действительного значения функции в Big-O ( или Big-Theta) асимптотический класс сложности функции.

Для Биг-О, вероятно, достаточно сказать O(n^(n+1)), но для Биг-Тета этого недостаточно.

Вот проблема, связанная с Big-O и факториалами: https://math.stackexchange.com/questions/323290/stirlings-approximation

Answer 2

Позволяет немного алгебры ....

  N!      =  N x (N - 1) x (N - 2) x ... 1    // by definition

  N! x N  =  N x (N x (N - 1) x (N - 2) x ... 1)

          =  (N + 1 - 1) x (N x (N - 1) x (N - 2) x ... 1)

          =  ((N + 1) x N x (N - 1) x (N - 2) x ... 1) 
              - (N x (N - 1) x (N - 2) x ... 1)

          =  (N + 1)! - N!

Теперь, "интуитивно очевидно" ¹ , что O((N + 1)! - N!) - это то же самое, что и O((N+1)!) ... и это можно доказать из первых принципов.

Кроме того, «интуитивно очевидно», что O(N!N) в N раз дороже, чем O(N!), что переводит его в другой класс сложности. (Также как O(N) и O(N^2) - это разные классы сложности!)

---

Но вот в чем дело. Класс сложности O(N!) явно проблематичен для практических вычислений, так как N становится большим. Это существенно хуже, чем простая экспонента.

  N!   ~=  N^N for large N  // by Stirling's Approximation

  N^N   =  e^(NlogN)

  e^(NlogN) >> e^N for large N

Так что, в основном, если у вас O(N!) или O(N!N), у вас большая проблема ... в любом случае.

---

^{1 - Утверждения типа «интуитивно очевидный» не являются правильной математикой. Очевидно.}

Answer 3

O (n! * N) довольно высокая сложность. Но так как есть умножение, вы не можете удалить второе n. Но если бы была такая зависимость, как o (n! + N), то n можно было бы опустить, поскольку для больших значений n n несущественно по сравнению с n!