Java O(n!) 的例子？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3953244/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Example of O(n!)?
提问by Derek Long
What is an example (in code) of a O(n!)function? It should take appropriate number of operations to run in reference to n; that is, I'm asking about time complexity.
什么是O(n!)函数的示例（在代码中）？应参考运行适当数量的操作n；也就是说，我问的是时间复杂度。
采纳答案by sepp2k
There you go. This is probably the most trivial example of a function that runs in O(n!)time (where nis the argument to the function):
你去吧。这可能是一个O(n!)及时运行的函数的最简单的例子（函数n的参数在哪里）：
void nFacRuntimeFunc(int n) {
for(int i=0; i<n; i++) {
nFacRuntimeFunc(n-1);
}
}
回答by codaddict
One classic example is the traveling salesman problemthrough brute-force search.
一个经典的例子是通过蛮力搜索的旅行商问题。
If there are Ncities, the brute force method will try each and every permutation of these Ncities to find which one is cheapest. Now the number of permutations with Ncities is N!making it's complexity factorial (O(N!)).
如果有N城市，蛮力法将尝试这些N城市的每一个排列，以找到哪个最便宜。现在，N城市的排列数量N!使其复杂性为阶乘 ( O(N!))。
回答by Armen Tsirunyan
the simplest example :)
最简单的例子:)
pseudocode:
伪代码：
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!)
there you go :)
你去吧:)
As a real example - what about generating all the permutations of a set of items?
作为一个真实的例子 - 生成一组项目的所有排列怎么样？
回答by Jungle Hunter
Finding the determinant with expansion by minors.
寻找未成年人扩张的行列式。
Very good explanation here.
这里很好的解释。
# 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;
}
Code from here. You will also find the necessary .hppfiles there.
回答by Margus
There are problems, that are NP-complete(verifiable in nondeterministic polynomial time). Meaning if input scales, then your computation needed to solve the problem increases more then a lot.
存在问题，即NP-complete（可在不确定的多项式时间内验证）。这意味着如果输入可以扩展，那么解决问题所需的计算会增加很多。
Some NP-hardproblemsare: Hamiltonian path problem(open img ), Travelling salesman problem(open img )
Some NP-completeproblemsare: Boolean satisfiability problem (Sat.)(open img ), N-puzzle(open img ), Knapsack problem(open img ), Subgraph isomorphism problem(open img ), Subset sum problem(open img ), Clique problem(open img ), Vertex cover problem(open img ), Independent set problem(open img ), Dominating set problem(open img ), Graph coloring problem(open img ),
一些NP-hard问题是：哈密顿路径问题（开放 img）、旅行商问题（开放 img）
一些NP-complete问题是：布尔可满足性问题（周六）（开放 img）、N 拼图（开放 img）、背包问题（开放 img）、子图同构问题（开放img），子集求和问题（开放img），团问题（开放img），顶点覆盖问题( open img),独立集问题( open img),支配集问题( open img),图着色问题( open img),
Source: link
来源：链接
回答by Bill the Lizard
See the Orders of common functionssection of the Big O Wikipediaarticle.
请参阅Big O 维基百科文章的常用函数顺序部分。
According to the article, solving the traveling salesman problemvia brute-force search and finding the determinantwith expansion by minorsare both O(n!).
回答by nonopolarity
In Wikipedia
在维基百科
Solving the traveling salesman problem via brute-force search; finding the determinant with expansion by minors.
通过蛮力搜索解决旅行商问题；通过未成年人的扩展找到行列式。
http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions
http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions
回答by MdaG
回答by Gabi Purcaru
I think I'm a bit late, but I find snailsortto be the best example of O(n!) deterministic algorithm. It basically finds the next permutation of an array until it sorts it.
我想我有点晚了，但我发现snailsort是 O(n!) 确定性算法的最佳示例。它基本上会找到数组的下一个排列，直到对其进行排序。
It looks like this:
它看起来像这样：
template <class Iter>
void snail_sort(Iter first, Iter last)
{
while (next_permutation(first, last)) {}
}
回答by user477556
The recursive method you probably learned for taking the determinant of a matrix (if you took linear algebra) takes O(n!) time. Though I dont particularly feel like coding that all up.
您可能学到的用于获取矩阵行列式的递归方法（如果您使用线性代数）需要 O(n!) 时间。虽然我并不特别喜欢编码。
