a 问

前两种算法都是完全随机的，所有的置换都是等可能的。
至于第三种算法也是等可能的，证明可以参考： 第二章 检验复杂度分析的正确性
值得一提的是变式：
image.png

27种等可能的交换

开始的时候，我不理解什么是27种等可能的交换。现说明如下：

  • 对于 A[0] 来说，可以交换的是A[0]/A[1]/A[2],一共三种。
  • 对于A[1] 来说，可以交换的是 A[0]/A[1]/A[2]，三种
  • 对于A[2] 来说，可以交换的是 A[0]/A[1]/A[2]，三种。

它们互相组合，333=27种可能，这二十七种可能对应着27个等可能的合法置换（可以重复）。

b 问

该问要求算分析时间复杂度。
用大O标记表示的时间复杂度不能简单被认为是输入是最坏情况下的时间复杂度。
也可以分成不同的情况：
在平均的输入状态下（有好，有坏），所得到的时间复杂度（也就是运行时间的上界）。
若输入一直是最坏情况下，所得到的时间复杂度。
输入状态非常好，所得到的时间复杂度。
【输入状态有时候也可以替换成 随机数的情况，如果随机数一直不满足条件，就等价于最坏的输入状态，见D问】
关于这些概念的区别可以参考：快速排序最好，最坏，平均复杂度分析
一般情况下，我们求的是第一种时间复杂度。

据此，有答案：

image.png

在级数的推导中，用到了以下数学原理：

image.png

C 问

官方答案是这样说的：
image.png
没能理解，为什么“当N很大的时候，会有激烈的增长，使得它看起来不是线性的”。（存疑）
下面是我实现的代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int randInt(int i,int j){ //生成的是[i,j) 范围内的整数
  4.     return rand()%(j-i)+i;
  5. }
  6. void printArr(int arr[],int N){
  7.     for(int i=0;i<N;i++){
  8.         printf("%d ",arr[i]);
  9.     }
  10.     printf("\n");
  11. }
  12. void method_1(int arr[],int N){
  13.     arr[0]=randInt(1,N+1);
  14.     for(int i=1;i<N;i++){    
  15.         int t=randInt(1,N+1);
  16.         int key=0;
  17.         for(int j=0;j<i;j++){
  18.             if(t==arr[j]){
  19.                 key=1;
  20.                 break;
  21.             }
  22.         }
  23.         if(key==0){
  24.             arr[i]=t;
  25.         }else{
  26.             i--;
  27.         } 
  28.     }
  29. }
  30. void method_2(int arr[],int N){
  31.     int t=randInt(1,N+1);
  32.     int used[N]={0};
  34.     arr[0]=t;
  35.     used[t]=1;
  36.     int i=1;
  37.     while(i<N){
  38.         int randNumber=randInt(1,N+1);
  39.         if(used[randNumber]==1){
  40.             continue;
  41.         }else{
  42.             arr[i]=randNumber;
  43.             used[randNumber]=1;
  44.             i++;
  45.         }
  46.     }
  47. }
  48. void method_3(int arr[],int N){
  49.     for(int i=0;i<N;i++){
  50.         arr[i]=i+1;
  51.     }
  52.     for(int i=1;i<N;i++){
  53.         swap(arr[i],arr[randInt(0,i)]);
  54.     }
  55. }
  58. int main(){
  59.     int N;
  60.     while(~scanf("%d",&N)){
  61.         clock_t start=clock();
  62.         int arr[N];
  63.         //method_1(arr,N);
  64.         //method_2(arr,N);
  65.         method_3(arr,N);
  66.         clock_t end=clock();
  67.         double time=(double)(end-start)/CLOCKS_PER_SEC;
  68.         double msTime=time*1000;
  69.         cout<<"msTime="<<msTime<<endl;
  70.         cout<<"msTime/n="<<msTime/N<<endl;
  71.         cout<<"msTime/nlogN="<<msTime/(N*log(N))<<endl;
  72.         cout<<"msTime/n^2="<<msTime/(N*N)<<endl;
  73.         cout<<"msTime/n^2*logN="<<msTime/(N*N*log(N))<<endl;
  75.     }     
  76. }

结论如下：
如果 N 过小，则时间上有很多因素干扰，不够稳定，但是如果 N 过大，则数组过大导致不能运行和计算，在恰当的范围内，又不能很好的看出 T(n)/f(n) 的性质，不能精确的用代码判断出时间复杂度的大小。
参考：习题2.8
c++计时函数：C/C++程序计时函数

D 问

image.png