这段代码的复杂度是多少？

Question

我的代码是：

vector<int> permutation(N); 
vector<int> used(N,0);

void try(int which, int what) {
  // try taking the number "what" as the "which"-th element
  permutation[which] = what;
  used[what] = 1;

  if (which == N-1)
    outputPermutation();
  else
   // try all possibilities for the next element
  for (int next=0; next<N; next++)
    if (!used[next])
    try(which+1, next);

  used[what] = 0;
} 

int main() {
  // try all possibilities for the first element
  for (int first=0; first<N; first++)
    try(0,first);
}

我从遇到这段代码的某个网站学习复杂性。根据我的理解，以下行迭代了 N 次。所以复杂度是 O(N).

for (int first=0; first<N; first++)

接下来考虑递归调用

for (int next=0; next<N; next++)
   if (!used[next])
    try(which+1, next);

因此，此递归调用涉及的步骤数 = t(n) = N.c + t(0)。（其中是某个常数步骤）我们可以说对于这一步，复杂度是 = O(N)。

因此总复杂度为 - O(N.N) = O(N^2)

我的理解对吗？谢谢！

Answer 1

这是一个递归函数。函数"try"递归调用自己，所以在main()中有一个循环，在try()中有一个循环，在递归调用try()中有一个循环，在下一个递归调用try()中有一个循环等等。

你需要非常仔细地分析这个函数的作用，否则你会得到一个完全错误的结果（就像你所做的那样）。您实际上可以考虑运行这段代码，其中 N = 1 到 20 的值并测量时间。你会发现它绝对不是 O (N^2)。实际上，不要跳过 N 的任何值；你会明白为什么。

Answer 2

此算法的复杂度为 O(N!)（如果 outputPermutation 需要 O(N)，则甚至为 O(N! * N)，这似乎是可能的）。

该算法输出0..N个自然数的所有无重复排列。

递归函数 try 本身依次尝试将 N 个元素放入位置 which 并且每次尝试都会递归调用自身以获取下一个 which 位置，直到 which达到 N-1。此外，对于每个迭代 try 实际上被调用 (N - which) 次，因为在每个级别上一些元素被标记为 used 以消除重复。因此，该算法需要 N * (N - 1) * (N - 2) ... 1 个步骤。

这段代码的复杂度是多少？

What will be the complexity of this code?

algorithm

recursion

complexity-theory

big-o

time-complexity