noj-1324.png
這是開端痛悯。
然后產(chǎn)生了以下兩個程序：
void perms1(int m)
{
static int b[N]={0};
static char use[N]={0};
if(m >= n)
{
for(int i=0;i<n;i++)
printf("%d ",b[i]);
printf("\n");
return ;
}
for(int i=0;i<n;i++)
{
if(use[i] == 0)
{
use[i] = 1;
b[m] = a[i];
dfs(m+1);
use[i] = 0;
}
}
return ;
}
void perms2(int m)
{
if(m >= n)
{
for(int i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
return ;
}
for(int i=m,t=0;i<n;i++)
{
t = a[i]; a[i] = a[m]; a[m] = t;
perms(m+1);
t = a[i]; a[i] = a[m]; a[m] = t;
}
return ;
}
兩個函數(shù)進行全排列后都可以按照字典序的順序輸出(不符合題意是因為后來歷經(jīng)多次修改伯铣，思想是相同的)慢洋。
比較 ：
空間：perms1為O(n),perms2為O(1)吹泡。
perms1使用了一倍的附加存儲空間和相同數(shù)量的標記位盟庞。
perms2使用了一個變量用于交換阶剑。
時間：相同 跃巡。
遞歸層數(shù)相同。
函數(shù)內(nèi)的循環(huán)次數(shù)不同牧愁，perms1更多的做了一些無用功素邪。
由于交換，perms2在循環(huán)內(nèi)的賦值操作比perms1多一倍猪半。
實際測試中兩個函數(shù)時間相差極小兔朦，大多數(shù)情況下perms2更快。
猜想：CPU的cache?
