Можно ли упростить O (n! + N)?

Question

Я читал о временной сложности и натолкнулся на временную сложность O (n! + N). Можно ли это упростить? Если да, как бы вы это сделали?

Answer 1

Как намеков, для п ≥ 2, обратите внимание, что

п! + n ≤ n! + n! = 2n!

и

н! + n> n!

Можете ли вы использовать эти наблюдения, чтобы найти более простой способ выражения O (n! + N)?

Надеюсь, это поможет!

Answer 2

Ответы @templatetypedef верны и помогут вам принять решение в этом конкретном случае, мы можем попытаться предоставить вам больше инструментов для его использования на практике.

Прямо из big O определения вы можете сказать:

1. O(f(n)+g(n)) = O(f(n)) + O(g(n))
2. O(k f(n)) = k O(f(n)) = O(f(n))
3. если f(n) является O(n) то f(n) является O(n!)

Где 1 и 2 пришли непосредственно из limsup свойства и 3 - простое упражнение. С помощью этих 3 предложений мы можем сказать:

O (п + п!) = O (п) + О (п) = 2 O = O (п!)