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

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

该算法的复杂度为O(N!)(甚至O(N！* N)，如果outputPermutation采用O(N) (这似乎是可能的)。

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

递归函数try本身依次尝试将N个元素放置在which位置，每次尝试，它都递归地为下一个which位置调用自己，直到which达到N1为止。另外，对于每次迭代，try实际上被调用(N - which)次，因为在每个级别上，为了消除重复，某些元素被标记为used。因此，该算法采用N*(N-1)*(N-2).1步。

Answer 2

它是一个递归函数。函数" try“递归地调用自己，因此main ()中有一个循环，try ()中有一个循环，用于try ()的递归调用中有一个循环，下一个递归调用中有一个循环用于try ()，等等。

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