algorithm - 当 f(n) = O(n!) 且 k=n*(n-1) 时 f(k) 的复杂度

Question

我有以下问题。假设我们有函数 f(n)。 f(n) 的复杂度为 O(n!)。但是，还有参数k=n*(n-1)。我的问题是 - f(k) 的复杂度是多少？是 f(k)=O(k!/k^2) 还是类似的东西，考虑到 k 和 之间存在二次关系n?

Answer 1

计算复杂度是根据输入的大小来解释的。因此，如果 f(n) = O(n!) 当您的输入是 n 时，则 f(k) = O(k!) 当您的输入是 k 时。

因此，您无需为函数 f(n) 的每个输入值计算复杂度。例如，f(2) = O(2!)，您不需要像 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))