什么是一个 O(n!)
函数的代码示例?它应该在参考 n
的情况下以适当数量的操作运行;也就是说,我正在询问时间复杂度。
什么是一个 O(n!)
函数的代码示例?它应该在参考 n
的情况下以适当数量的操作运行;也就是说,我正在询问时间复杂度。
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)
。
你是正确的,递归调用应该需要恰好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 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);
}
在 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。谢谢。
这是一个带有复杂度 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;
}
@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!)。虽然我不太想编写这个算法。