什么是O(n!)函数的示例（在代码中）？参考 ; 应该需要适当数量的操作来运行n；也就是说，我问的是时间复杂度。
问问题
79738 次
17 回答
121
你去吧。这可能是O(n!)及时运行的函数的最简单示例（函数n的参数在哪里）：
void nFacRuntimeFunc(int n) {
for(int i=0; i<n; i++) {
nFacRuntimeFunc(n-1);
}
}
于 2010-10-17T12:42:17.620 回答
51
一个典型的例子是通过蛮力搜索的旅行商问题。
如果有N城市，蛮力方法将尝试这些N城市的每一个排列，以找出哪个最便宜。N现在，城市排列的数量N!使其复杂性成为因子 ( O(N!))。
于 2010-10-17T12:41:43.960 回答
10
请参阅Big O Wikipedia文章的常用函数顺序部分。
于 2010-10-17T13:03:44.563 回答
8
任何计算给定数组的所有排列的算法都是O(N!).
于 2010-11-02T13:44:29.610 回答
6
存在一些问题NP-complete（在非确定性多项式时间内可验证）。这意味着如果输入扩展，那么解决问题所需的计算量就会增加很多。
一些NP-hard问题是：哈密顿路径问题（open img），旅行商问题（open img）
一些NP-complete问题是：布尔可满足性问题（星期六）（open img），N-puzzle（open img），背包问题（open img），子图同构问题（open img）、子集和问题（open img）、Clique问题（open img）、顶点覆盖问题( open img )、独立集问题( open img )、支配集问题( open img )、图着色问题( open img )、
来源：链接
于 2010-10-17T12:43:59.457 回答
6
我想我有点晚了，但我发现snailsort是 O(n!) 确定性算法的最佳示例。它基本上找到数组的下一个排列，直到对它进行排序。
它看起来像这样：
template <class Iter>
void snail_sort(Iter first, Iter last)
{
while (next_permutation(first, last)) {}
}
于 2010-10-17T18:38:54.273 回答
5
通过未成年人的扩展找到行列式。
很好的解释在这里。
# include <cppad/cppad.hpp>
# include <cppad/speed/det_by_minor.hpp>
bool det_by_minor()
{ bool ok = true;
// dimension of the matrix
size_t n = 3;
// construct the determinat object
CppAD::det_by_minor<double> Det(n);
double a[] = {
1., 2., 3., // a[0] a[1] a[2]
3., 2., 1., // a[3] a[4] a[5]
2., 1., 2. // a[6] a[7] a[8]
};
CPPAD_TEST_VECTOR<double> A(9);
size_t i;
for(i = 0; i < 9; i++)
A[i] = a[i];
// evaluate the determinant
double det = Det(A);
double check;
check = a[0]*(a[4]*a[8] - a[5]*a[7])
- a[1]*(a[3]*a[8] - a[5]*a[6])
+ a[2]*(a[3]*a[7] - a[4]*a[6]);
ok = det == check;
return ok;
}
于 2010-10-17T12:43:23.707 回答
4
最简单的例子:)
伪代码：
input N
calculate N! and store the value in a vaiable NFac - this operation is o(N)
loop from 1 to NFac and output the letter 'z' - this is O(N!)
你去吧:)
作为一个真实的例子 - 生成一组项目的所有排列怎么样？
于 2010-10-17T12:42:29.307 回答
2
在维基百科中
通过蛮力搜索解决旅行商问题；通过未成年人的扩展找到行列式。
http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions
于 2010-10-17T13:04:37.137 回答
1
在 C# 中
这不是空间复杂度的 O(N!) 吗？因为，C# 中的字符串是不可变的。
string reverseString(string orgString) {
string reversedString = String.Empty;
for (int i = 0; i < orgString.Length; i++) {
reversedString += orgString[i];
}
return reversedString;
}
于 2011-02-18T16:17:36.157 回答
1
printf("Hello World");
是的，这是 O(n!)。如果你认为不是，我建议你阅读 BigOh 的定义。
我只添加了这个答案，因为人们不得不总是使用 BigOh，不管他们的实际意思是什么。
例如，我很确定这个问题是要问 Theta(n!)，至少是 cn！步数不超过Cn！一些常数 c, C > 0 的步骤，但选择使用 O(n!) 代替。
另一个例子：Quicksort is O(n^2) in the worst case虽然在技术上是正确的（在最坏的情况下，即使堆排序也是 O(n^2)！），但它们的实际意思是Quicksort is Omega(n^2) in the worst case.
于 2011-02-18T17:19:12.800 回答
1
你是对的，递归调用应该正好是 n！时间。这是一个类似测试 n 个不同值的阶乘时间的代码。内循环运行 n! j 的不同值的时间，所以内循环的复杂度是 Big O(n!)
public static void NFactorialRuntime(int n)
{
Console.WriteLine(" N Fn N!");
for (int i = 1; i <= n; i++) // This loop is just to test n different values
{
int f = Fact(i);
for (int j = 1; j <= f; j++) // This is Factorial times
{ ++x; }
Console.WriteLine(" {0} {1} {2}", i, x, f);
x = 0;
}
}
这是 n = 5 的测试结果，它精确地迭代阶乘时间。
N Fn N!
1 1 1
2 2 2
3 6 6
4 24 24
5 120 120
时间复杂度为 n 的精确函数！
// Big O(n!)
public static void NFactorialRuntime(int n)
{
for (int j = 1; j <= Fact(i); j++) { ++x; }
Console.WriteLine(" {0} {1} {2}", i, x, f);
}
于 2017-02-03T06:51:32.820 回答
0
Bogosort是我遇到的唯一一个涉足 O(n!) 领域的“官方”。但这不是保证的 O(n!)，因为它本质上是随机的。
于 2010-10-17T14:32:50.620 回答
0
您可能学到的用于获取矩阵行列式的递归方法（如果您使用线性代数）需要 O(n!) 时间。虽然我并不特别喜欢编码。
于 2010-10-18T10:37:46.753 回答
0
@clocksmith你是绝对正确的。这不是计算 n!。也不是 O(n!)。我运行它收集了下表中的数据。请比较第 2 列和第 3 列。（#nF 是调用 nFacRuntimeFunc 的次数）
n #nF n!
0 0 1
1 1 1
2 4 2
3 15 6
4 65 24
5 325 120
6 1956 720
7 13699 5040
很明显，如果性能比 O(n!) 差得多。下面是计算 n! 的示例代码！递归地。你会注意到它的 O(n) 顺序。
int Factorial(int n)
{
if (n == 1)
return 1;
else
return n * Factorial(n-1);
}
于 2016-12-17T21:29:20.280 回答
0
添加向上 k 功能
这是一个复杂度为 O(n!) 的函数的简单示例，给定一个 int 数组和一个整数 k。如果数组 x+y = k 中有两项，则返回 true，例如：如果 tab 为 [1, 2, 3, 4] 且 k=6，则返回值为 true，因为 2+4=6
public boolean addToUpK(int[] tab, int k) {
boolean response = false;
for(int i=0; i<tab.length; i++) {
for(int j=i+1; j<tab.length; j++) {
if(tab[i]+tab[j]==k) {
return true;
}
}
}
return response;
}
作为奖励，这是一个使用 jUnit 的单元测试，它工作正常
@Test
public void testAddToUpK() {
DailyCodingProblem daProblem = new DailyCodingProblemImpl();
int tab[] = {10, 15, 3, 7};
int k = 17;
boolean result = true; //expected result because 10+7=17
assertTrue("expected value is true", daProblem.addToUpK(tab, k) == result);
k = 50;
result = false; //expected value because there's any two numbers from the list add up to 50
assertTrue("expected value is false", daProblem.addToUpK(tab, k) == result);
}
于 2019-06-04T14:50:59.060 回答
0
在 JavaScript 中：
// O(n!) Time Complexity
const {performance} = require('perf_hooks');
const t0 = performance.now()
function nFactorialRuntime(input){
let num = input;
if (input === 0) return 1;
for(let i=0; i< input; i++){
num = input * nFactorialRuntime(input-1);
}
return num;
}
const t1 = performance.now()
console.log("The function took: " + (t1 - t0) + " milliseconds.")
nFactorialRuntime(5);
对于节点 8.5+，您需要首先包含perf_hooks模块的性能。谢谢你。
于 2021-09-23T15:57:28.657 回答