回溯算法(全排列问题)_回溯法求全排列问题的时间复杂度

1.全排列的定义和公式：

从n个数中选取m（m<=n）个数按照一定的顺序进行排成一个列，叫作从n个元素中取m个元素的一个排列。由排列的定义，显然不同的顺序是一个不同的排列。从n个元素中取m个元素的所有排列的个数，称为排列数。从n个元素取出n个元素的一个排列，称为一个全排列。全排列的排列数公式为n!，通过乘法原理可以得到。

2.时间复杂度：

n个数（字符、对象）的全排列一共有n!种，所以全排列算法至少时间O(n!)

的。如果要对全排列进行输出，那么输出的时间要O(n∗n!)，因为每一个排列都有n个数据。

算法思路：全排列可以看做固定前i位，对第i+1位之后的再进行全排列，比如固定第一位，后面跟着n-1位的全排列。那么解决n-1位元素的全排列就能解决n位元素的全排列了，这样的设计适合用递归实现。

举例：简单点拿常数1,2,3来说:首先对1进行全排列,首先保持第一个不变，对【2,3】进行全排列。同样地，我们先保持2不变，对【3】进行全排列。故排列为【1，2，3】 。接下来不能以2打头了，2，3相互交换，得到

【1，3，2】。 所以1的全排列为【1，2，3】,【1，3，2】 。同理对2,3元素同样处理。

递归代码：

void prim(int a[],int start,int end){
       if(start==end){
             for(int i = 0;i<=end;i++){   //当递归到开始节点与结束点相同时,打印结果。
                cout<<a[i]<<" ";
             }
                cout<<endl;
       }
       /*
         *这里的递归理解:for循环实现对数组中第一个元素与其他元素交换(当然也包括本身),
         *然后进行相应递归求得其他每个元素对应的排列。
         *需要注意的是:交换后,要记得"回溯",保证元素的正常递归顺序。
       */
       else{
            for(int i = start;i<=end;i++){
                swap(a[start],a[i]);     //与当前开始交换位置.
                prim(a,start+1,end);
                swap(a[start],a[i]);     //交换位置,换回原来的情况。
            }
       }
}

完整代码:

/*
  @全排列问题
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
void swap(int &a,int &b){              //注意要取地址(交换的应为值与位置)
     int item = a;
     a = b;
     b = item;
}
void prim(int a[],int start,int end){
       if(start==end){
             for(int i = 0;i<=end;i++){   //当递归到开始节点与结束点相同时,打印结果。
                cout<<a[i]<<" ";
             }
                cout<<endl;
       }
       /*
         *这里的递归理解:for循环实现对数组中第一个元素与其他元素交换(当然也包括本身),
         *然后进行相应递归求得其他每个元素对应的排列。
         *需要注意的是:交换后,要记得"回溯",保证元素的正常递归顺序。
       */
       else{
            for(int i = start;i<=end;i++){
                swap(a[start],a[i]);     //与当前开始交换位置.
                prim(a,start+1,end);
                swap(a[start],a[i]);     //交换位置,换回原来的情况。
            }
       }
}
int main()
{
      int a[10] = {1,2,3};
      cout<<"元素全排列为:"<<endl;
      prim(a,0,2);
      return 0;
}

【注1】swap(str[i],str[j]) //交换回来

当我们对序列进行交换之后，就将交换后的序列除去第一个元素放入到下一次递归中去了，递归完成了再进行下一次循环。这是某一次循环程序所做的工作，这里有一个问题，那就是在进入到下一次循环时，序列是被改变了。可是，如果我们要假定第一位的所有可能性的话，那么，就必须是在建立在这些序列的初始状态一致的情况下,所以每次交换后，要还原，确保初始状态一致。