Сложность f (k), когда f (n) = O (n!) И k = n * (n-1)

Question

У меня следующая проблема. Предположим, у нас есть функция f(n). Сложность f(n) составляет O(n!). Однако есть также параметр k=n*(n-1). У меня вопрос - в чем сложность f(k)? Это f(k)=O(k!/k^2) или что-то в этом роде, учитывая, что между k и n?

существует квадратичное соотношение?

Answer 1

Считаете ли вы, что существует m , такой, что n , который вы использовали в вашем f (n), равен m * (m - 1) .

Это меняет сложность?

---

n в f (n) = O (n!) Представляет все действительные входные данные.

Вы пытаетесь передать переменную k , фактическое значение которой в терминах другой переменной равно n * (n - 1) . Это не меняет сложности. Это будет только O (k!).

Answer 2

Вычислительная сложность интерпретируется исходя из размера ввода. Следовательно, если f(n) = O(n!), когда ваш ввод n, то f(k) = O(k!), когда ваш ввод k.

Следовательно, вам не нужно вычислять сложность для каждого значения ввода для функции f(n). Например, f(2) = O(2!), вам не нужно вычислять сложность f(10) лайков O((5*2)!) как 10 = 5 * 2 и пытаться упростить ее на основе значения 2!. Мы можем сказать f(10) = O(10!).

Во всяком случае, если вы хотите вычислить (n*(n-1))! = (n^2 - n)!(n^2 - n + 1)...(n^2 - n + n) /(n^2 - n + 1)...(n^2 - n + n) = (n^2)!/\theta(n^3) = O((n^2)!/n^(2.9))