algorithm - 该代码的复杂性是什么？

我的代码是:

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)

我的理解正确吗？
谢谢!

最佳答案

该算法的复杂度为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个步骤。