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个回答
1

printf("你好，世界");

是的，这是O(n!)。如果您认为不是，请阅读BigOh的定义。

我之所以添加了这个答案，是因为人们总是有annoying habit在实际含义不明确时仍然使用BigOh。

例如，我很确定问题本意是要问Theta(n!)，至少cn!步骤，而不超过某些常数c、C > 0的Cn!步骤，但选择使用了O(n!)。

另一个例子：快速排序在最坏情况下为O(n^2)，虽然技术上是正确的（甚至堆排序在最坏情况下也是O(n^2)！），但他们实际上想表达的是快速排序在最坏情况下为Omega(n^2)。

1
尽管在数学上是正确的，但O(n)符号几乎一直被宽泛使用，即使是那些更好懂的人也是如此。特别地，使用比严格必要的更高的O类被认为是具有欺骗性的；因此，任何从业者都不会将O(n)算法称为O(n²)，尽管任何属于O(n)的算法也（根据定义）属于O(n²)。 - tucuxi
这似乎更适合作为评论而不是答案，因为它仅仅指出了问题中的技术细节，并明显忽略了所问的重点。 - Bernhard Barker
1

你是正确的，递归调用应该需要恰好n！的时间。这里有一段代码，用于测试不同值的阶乘时间。内部循环针对不同的j值运行n！次，因此内部循环的复杂度为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);
    }
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);

对于 Node 8.5+，您需要首先从 perf_hooks 模块中引入 performance。谢谢。

0

加到 k 的函数

这是一个带有复杂度 O(n!) 的简单示例函数，它接受一个整数数组和一个整数 k 作为参数，并在其中返回 true 如果该数组中存在两个元素 x+y=k。例如：如果数组 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);
    }
这不是O(n^2)吗？ - Luniam
@Luniam 不是这样的，因为如果你能注意到第二个循环并不是从数组的第一个索引开始的。我不知道你是否明白我的意思，请在评论中回复我，如果你需要更多的解释！ - Achraf Bellaali
0

Bogosort 是我遇到的唯一一个进入 O(n!) 领域的“官方”算法。但它并不是保证 O(n!)，因为它是随机的。

0

如果你学过线性代数，那么你可能学过用递归方法求矩阵行列式的方式，但这种方法的时间复杂度为O(n!)。虽然我不太想编写这个算法。

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