算法1
(暴力枚举) $O(n*n!)$
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
bool st[N];
int a[N];
int n;
void dfs(int u)
{
if(u == n)
{
for(int i = 1; i <= n; i ++ )
cout << a[i] << ' ';
cout << endl;
return ;
}
for(int i = 1; i <= n; i ++ )
{
if(st[i]) continue;
st[i] = 1;
a[u + 1] = i;
dfs(u + 1);
st[i] = 0;
}
}
int main()
{
cin >> n;
dfs(0);
}
算法2
stl $O(n*n!)$
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
typedef long long ll;
int a[N];
int main()
{
int n;
cin >> n;
ll s = 1;
for(int i = 1; i <= n; i ++ )
{
s *= i;
a[i] = i;
}
for(int i = 1; i <= s; i ++ )
{
for(int j = 1; j <= n; j ++ )
cout << a[j] << ' ';
cout << endl;
next_permutation(a + 1, a + n + 1);
}
}
都是$n^{n!}$
应该是我时间复杂度算错了,谢谢指正
说错了$n * n!$
~时间复杂度不是一样的吗~
我百度了下next_permutation(a + 1, a + n + 1)的时间复杂度是o(n)
递归的复杂度不知道我算的对不对..流汗.jpg