文章图片
noj-1324.png
这是开端。
然后产生了以下两个程序：
void perms1(int m)
{
static int b[N]={0};
static char use[N]={0};
if(m >= n)
{
for(int i=0;
ivoid perms2(int m)
{
if(m >= n)
{
for(int i=0;
i两个函数进行全排列后都可以按照字典序的顺序输出(不符合题意是因为后来历经多次修改，思想是相同的)。
比较 ：
【2018-11-10-noj1324】空间：perms1为O(n),perms2为O(1)。
perms1使用了一倍的附加存储空间和相同数量的标记位。
perms2使用了一个变量用于交换。
时间：相同 。
递归层数相同。
函数内的循环次数不同，perms1更多的做了一些无用功。
由于交换，perms2在循环内的赋值操作比perms1多一倍。
实际测试中两个函数时间相差极小，大多数情况下perms2更快。
猜想：CPU的cache?
