我的代码是:
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 个步骤。
关于algorithm - 这段代码的复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31754988/