当 f(n) = O(n!) 且 k=n*(n-1) 时 f(k) 的复杂度
Complexity of f(k) when f(n) = O(n!) and k=n*(n-1)
我有以下问题。假设我们有函数 f(n)。 f(n) 的复杂度是 O(n!)。但是，还有参数k=n*(n-1)。我的问题是 - f(k) 的复杂度是多少？考虑到 k 和 n 之间存在二次关系，是 f(k)=O(k!/k^2) 还是类似的东西？
计算复杂度是根据输入的大小来解释的。因此，如果 f(n) = O(n!) 当您的输入是 n，那么当您的输入是 k 时 f(k) = O(k!)。
因此，您无需为函数 f(n) 的每个输入值计算复杂度。例如，f(2) = O(2!)，你不需要将f(10)的复杂度计算为O((5*2)!)的复杂度为10 = 5 * 2，并尝试根据[=19的值来简化它=].我们可以说 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))
你有没有想过有一个m，使得你在你的f(n)中使用的n等于m * (m - 1).
这会改变复杂性吗？
f(n) = O(n!) 中的 n 表示所有有效输入。
您正在尝试传递一个变量 k，其相对于另一个变量的实际值为 n * (n - 1)。这不会改变复杂性。它只会是 O(k!)。
我有以下问题。假设我们有函数 f(n)。 f(n) 的复杂度是 O(n!)。但是，还有参数k=n*(n-1)。我的问题是 - f(k) 的复杂度是多少？考虑到 k 和 n 之间存在二次关系，是 f(k)=O(k!/k^2) 还是类似的东西？
计算复杂度是根据输入的大小来解释的。因此，如果 f(n) = O(n!) 当您的输入是 n，那么当您的输入是 k 时 f(k) = O(k!)。
因此，您无需为函数 f(n) 的每个输入值计算复杂度。例如，f(2) = O(2!)，你不需要将f(10)的复杂度计算为O((5*2)!)的复杂度为10 = 5 * 2，并尝试根据[=19的值来简化它=].我们可以说 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))
你有没有想过有一个m，使得你在你的f(n)中使用的n等于m * (m - 1).
这会改变复杂性吗？
f(n) = O(n!) 中的 n 表示所有有效输入。
您正在尝试传递一个变量 k，其相对于另一个变量的实际值为 n * (n - 1)。这不会改变复杂性。它只会是 O(k!)。