sep*_*p2k 81
你去吧 这可能是一个在O(n!)时间上运行的函数的最简单的例子(函数n的参数在哪里):
void nFacRuntimeFunc(int n) {
for(int i=0; i<n; i++) {
nFacRuntimeFunc(n-1);
}
}
- 鉴于这是n!的一对一计算,这是O(n!)增长顺序的定义*. (31认同)
- @Derek长循环是O(n),因为用(n-1)递归调用你得到n*(n-1)*(n-2)*...*1 = n!所以函数是O(n!). (4认同)
- @AdamRobinson 这不是 n 的计算！根本不。它只是一个执行自身的函数！次。我也不会将其称为 n! 的“定义”！生长。这只是一个明显的例子。 (3认同)
- @Derek：肯定是`O（n！）`（更重要的是`Θ（n！）`）。是的，在循环中调用的函数的时间复杂度会影响循环的时间复杂度。如果循环执行了“ n”次，并且循环中的函数执行了“（n-1）！”步，则总共有“ n *（n-1）！”步。= n！`步骤将被执行。这就是您如何证明此函数的时间复杂度在Θ（n！）中的确切方法。 (2认同)
- @AdamRobinson 即使被赞成，您的评论也是完全错误的。计算 n! 只需要 O(n) 时间——一个带有乘法的 for 循环。类似地，n2 的计算不会花费 O(n2) 时间——它将是 O(1)，一次乘法。 (2认同)
cod*_*ict 38
一个典型的例子是通过暴力搜索的旅行商问题.
如果有N城市,蛮力方法将尝试这些N城市的每一个排列,以找出哪个最便宜.现在,N城市排列的数量正在N!变得复杂因子(O(N!)).
- @aioobe:因为问题是"什么是O(n!)问题",答案是"这里是一个",我不认为你必须明确地说O(n!). (6认同)
- 想象一下3个城市.要检查任何潜在的路线,您必须检查两个城市之间的距离两次.A-> B和B-> C.你必须从所有3个角落开始.将距离计算到第一个城市,总共进行3次检查,然后将从第二个城市到第3个城市的距离相加,共计6次检查.那是3!= 6.为4个城市执行此操作,支票变为24. (2认同)
存在的问题是NP-complete(在非确定性多项式时间内可验证).意思是如果输入缩放,那么解决问题所需的计算量会增加很多.
一些NP-hard问题是:哈密顿路径问题(open img),旅行商问题(open img)
一些NP-complete问题是:布尔可满足性问题(Sat.)(打开img),N-puzzle(打开img),背包问题(打开img),子图同构问题(打开img),子集求和问题(打开img),Clique问题(打开img),顶点覆盖问题(打开img),独立设置问题(打开img),支配设置问题(打开img),图形着色问题(打开img),
来源:链接
- NP代表Nondeterministic**Polynomial**,意味着比指数时间更快(但仅在理论上).在理论和实践中,因子比指数慢.所以,这完全无关紧要. (4认同)
寻找未成年人扩张的决定因素.
这里有很好的解释.
# 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;
}
我想我有点晚了,但我发现snailsort是O(n!)确定性算法的最好例子.它基本上找到了数组的下一个排列,直到它对它进行排序.
它看起来像这样:
template <class Iter>
void snail_sort(Iter first, Iter last)
{
while (next_permutation(first, last)) {}
}