这段代码的复杂性是什么？

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)= Nc + t(0).(其中是一些常数步)我们可以说,对于这一步,复杂度是= O(N).

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

我的理解是对的吗？谢谢!

Answer 1

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

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

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