Почему O (n * n * n!) Упрощается до O ((n + 2)!) При вычислении больших O

Question

Итак, я читал книгу о взломе кодов, и есть проблема, когда у нас есть функция, которая выполняет O (n * n * n!) Работу. Затем в книге говорится, что это можно выразить через O ((n + 2)!). Он также говорит, что O (n * n!) Может быть выражено через O ((n + 1)!). Я посмотрел во всех правилах, если перестановок и не нашел никакого способа логически туда добраться. Мой первый шаг был крутым, у меня есть O (n ^ 2 + n!), Что теперь? Я не знаю, какие шаги предпринять дальше.

Answer 1

Для расчета x! вы делаете x*(x-1)! рекурсивно, пока x-1==1, поэтому x!==(x-1)*(x-2)*...*1 равно O (n!). Поэтому, чтобы сделать x*x!, у нас есть (x-0)*(x-1)*...*1, который принимает один дополнительный вызов нашей рекурсивной функции (но в начале, с большим значением x), то есть (x+1)! итераций. Точно так же (x-0)*(x-0)*(x-1)*(x-2)*...*1==x²*x! требует (x+2)! вычислений функции для вычисления, следовательно, эффективность O ((n + 2)!).

Answer 2

Вы уже знаете (я думаю), что n! = 1*2*3*...*n. Так что n*n*n! = 1*2*3*...*n*n*n.

Поскольку n становится действительно большим, добавление 1 или 2 к фактору оказывает все более значимое влияние. Я не специалист, но с O() имеет значение либо степень n, либо, в нашем случае, число в выражении ()!. Что заставляет нас сократить это до 1*2*3*...*n*(n+1)*(n+2)=(n+2)!.

В конце концов, O(n*n*n!) может быть выражено O((n+2)!).