O(n!) 的示例？

Question

O(n!) 函数的示例（代码）是什么？参考 n 应该需要适当数量的操作来运行；也就是说，我问的是时间复杂度。

Answer 1

就这样吧。这可能是在 O(n!) 时间内运行的函数的最简单的示例（其中 n 是函数的参数）：

void nFacRuntimeFunc(int n) {
  for(int i=0; i<n; i++) {
    nFacRuntimeFunc(n-1);
  }
}

Answer 2

一个典型的例子是通过暴力搜索解决旅行推销员问题。

如果有 N 个城市，暴力法将尝试这 N 个城市的每一个排列，以找出哪一个最便宜。现在，N 个城市的排列数量为 N!，使其复杂性阶乘 (O(N!))。

Answer 3

请参阅常用函数的顺序部分.wikipedia.org/wiki/Big_O_notation" rel="noreferrer">Big O 维基百科文章。

根据该文章，通过暴力搜索解决旅行推销员问题并找到行列式 与 未成年人的扩展都是 O(n!)。

Answer 4

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

Answer 5

有一些问题，NP-complete（可在非确定性多项式时间内验证）。这意味着如果输入规模扩大，那么解决问题所需的计算量就会增加很多。

一些NP-hard问题是：哈密尔顿路径问题(打开图片), 旅行推销员问题( open图片)
一些NP完全问题是：布尔可满足性问题（周六）（打开图片），N-puzzle(打开img),背包问题(打开img ），子图同构问题(打开img), 子集和问题( 打开 img ), 派系问题(< a href="https://i.sstatic.net/SrtfF.png" rel="nofollow noreferrer"> 打开 img ), 顶点覆盖问题(打开img ) , 独立集问题( 打开 img ), 支配集问题(打开图片)，图形着色问题( open img < /a>），

来源：链接 1，链接 2

来源：链接

Answer 6

我想我有点晚了，但我发现 snailsort 是O(n!) 确定性算法的最佳示例。它基本上找到数组的下一个排列，直到对其进行排序。

它看起来像这样：

template <class Iter> 
void snail_sort(Iter first, Iter last)
{
    while (next_permutation(first, last)) {}
}

Answer 7

寻找未成年人扩张的行列式。

这里有很好的解释。

# 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 文件 。

Answer 8

最简单的例子 :)

伪代码：

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

就这样 :)

作为一个真实的例子 - 生成一组项目的所有排列怎么样？

Answer 9

在维基百科中

通过暴力搜索解决旅行推销员问题；寻找未成年人扩张的行列式。

http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

Answer 10

printf("Hello World");

是的，这是 O(n!)。如果你认为不是，我建议你阅读BigOh的定义。

我添加这个答案只是因为人们必须始终使用 BigOh 的恼人习惯，而不管它们的实际含义是什么。

例如，我很确定这个问题是想问 Theta(n!)，至少是 cn！步数不超过Cn！对于一些常数c，C>的步骤0，但选择使用 O(n!) 代替。

另一个例子：快速排序在最坏情况下是 O(n^2)，虽然技术上是正确的（即使是堆排序在最坏情况下也是 O(n^2)！），但它们实际上的意思是在最坏的情况下，快速排序是 Omega(n^2)。

Answer 11

在 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;
}

Answer 12

你是对的，递归调用应该恰好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);
    }

Answer 13

Bogosort 是我遇到的唯一一个冒险进入 O(n!)区域。但它并不能保证 O(n!)，因为它本质上是随机的。

Answer 14

您可能学到的用于求矩阵行列式的递归方法（如果您采用线性代数）需要 O(n!) 时间。尽管我不太想把这些全部编码出来。

Answer 15

Add to up 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);
    }

Answer 16

在 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);

对于 Node 8.5+，您需要首先包含 perf_hooks 模块的性能。谢谢。