logo标签列表

O(n!)的例子是什么？

javaalgorithmbig-ocomplexity-theoryfactorial
93

什么是一个 O(n!) 函数的代码示例？它应该在参考 n 的情况下以适当数量的操作运行；也就是说，我正在询问时间复杂度。

http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ - Charlie Collins
4
只是纠正一下，你的意思是Ω(n!) [渐近增长的下界]或者“时间与n!成比例”[上下界]，而不是O(n!) [渐近增长的上界]。因为O(n!)只是上界，许多算法以无趣的方式是O(n!)，因为它们是O(n)、O(n log n)、O(1)或类似的复杂度。 - jacobm
16个回答
141

这就是一个非常简单的例子，演示了一个运行时间为O(n!)（其中n是函数参数）的函数：

void nFacRuntimeFunc(int n) {
  for(int i=0; i<n; i++) {
    nFacRuntimeFunc(n-1);
  }
}
41
鉴于这是 n! 的一对一计算，因此这正是 O(n!) 增长阶数的确切定义。 - Adam Robinson
2
@Derek：这绝对是O(n!)（更重要的是Θ(n!)）。是的，循环中调用的函数的时间复杂度会影响循环的时间复杂度。如果循环执行了n次，并且循环中的函数执行了(n-1)!步骤，那么总共将执行n * (n-1)! = n!个步骤。这正是你证明该函数的时间复杂度为Θ(n!)的方法。 - sepp2k
5
@Derek Long 这个循环的时间复杂度为O(n)，因为它被递归调用了(n-1)次，所以最终的时间复杂度为n*(n-1)(n-2)...*1 = n!，因此这个函数的时间复杂度是O(n!)。 - josefx
3
@AdamRobinson，这根本不是 n! 的计算。它只是一个执行自身 n! 次的函数。我也不会称它为 n! 增长的“定义”。它只是一个清晰的例子。 - clocksmith
6
尽管您的评论已经被点赞，但它是完全错误的。 n! 的计算只需要O（n）的时间--一个带有乘法的for循环。同样，n²的计算不需要O（n²）的时间--它将是O（1），即单个乘法运算。 - defhlt
显示剩余5条评论
54

一个经典的例子是通过暴力搜索解决旅行商问题 (traveling salesman problem)。

如果有 N 个城市，暴力搜索方法会尝试每一种这些 N 个城市的排列组合，以找到最便宜的那一个。现在，具有 N 个城市的排列组合数为 N! ，使得其复杂度是阶乘级别的 (O(N!))。

我没有 DV，但可能是因为它没有示例代码，也没有提供大 O 符号表示法... - aioobe
7
@aioobe回答了一个问题：“什么是O(n!)问题”，他的回答是“这就是一个”，我认为您不必明确地提到O(n!)。 - Claudiu
2
想象有三个城市。为了检查任何潜在的路线，您必须两次检查两个城市之间的距离。A->B和B->C。您必须从所有三个角落开始。将距离总和到第一个城市，因此总共有3个检查，然后将第二个城市的距离总和到第三个城市，总共有6个检查。这是3！= 6。对于4个城市，请执行此操作，检查变为24。 - Eric Leschinski
10
9

任何计算给定数组所有排列组合的算法都是O(N!)的。

7

有些问题是NP-complete的（可以在非确定性多项式时间内验证）。这意味着如果输入规模增加，解决该问题所需的计算量将会迅速增长。

一些NP-hard问题包括：哈密顿回路问题（打开图像），旅行商问题（打开图像）
一些NP-complete问题包括：布尔可满足性问题(Sat.)（打开图像），N-数码问题（打开图像），背包问题（打开图像），子图同构问题（打开图像），子集和问题（打开图像），团问题（打开图像），顶点覆盖问题（打开图像），独立集问题（打开图像），支配集问题（打开图像），图着色问题（打开图像），

来源：链接1, 链接2

alt文本
来源：链接

5
NP代表非确定性多项式，意思是比指数时间更快（但仅在理论上）。阶乘在理论和实践中都比指数慢，因此这完全不相关。 - Potatoswatter
6
我知道我有点晚了，但我认为snailsort是O(n!)确定性算法的最佳例子。它基本上会找到数组的下一个排列，直到将其排序。
它的样子是这样的：
template <class Iter> 
void snail_sort(Iter first, Iter last)
{
    while (next_permutation(first, last)) {}
}
由于n！可以定义为对n个对象进行排列的方式数量，因此这是我最喜欢的例子，尽管伪代码比c ++更好。;) - clocksmith
这显然需要O(n!)的时间是不明显的。next_permutation需要线性时间，因此朴素计算会给出O(n*n!)的时间（严格大于O(n!)）。你必须证明next_permutation在平均情况下需要O(1)时间才能使其起作用。 - Paul Hankin
值得注意的是，这个方法能够工作是因为 next_permutation 返回字典序中的下一个排列并返回 true，或者返回最小的排列（即排序后的排列）并返回 false 如果不存在下一个排列。 - Bernhard Barker
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;
}

这里的代码来自这里。您还可以在那里找到必要的.hpp文件。

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!)

这里有一个真实的例子——如何生成一组项目的所有排列？

2
1
在C#中，因为字符串是不可变的，所以这个程序的空间复杂度会达到O(N!)，你认为呢？
string reverseString(string orgString) {
    string reversedString = String.Empty;

    for (int i = 0; i < orgString.Length; i++) {
        reversedString += orgString[i];
    }

    return reversedString;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接