题目一：Strassen矩阵乘法问题延伸

将n阶矩阵分块为m*m的矩阵，用m阶矩阵乘积需要计算个 矩阵的乘积

算法描述

先算出m和k
然后利用Strassen算法算出
最后计算阶矩阵

时间复杂度分析

用Strassen矩阵乘法计算2个 * 矩阵的乘积需要计算的时间复杂度为O()
因此算法时间复杂度是O( * )

题目二：循环赛日程表问题延伸

算法描述

当选手n为时，每次递归计算个选手，将左上角递归算出的小块中所有数字按其相对位置抄到右下角，将左上角所有数字加n/2后按其相对位置抄到左下角，将左下角中所有数字安其对应位置抄到右上角。
对于一般的正整数n，当n时奇数时，增设一个虚拟选手n+1，将问题转换问n时偶数的情形。

递归函数

void tournament (int n){
  if(n==1){
    a[1][1]=1;
    return;
  }
  if(odd(n)){
    tournament (n+1);
    return;
  }
  tournament (n/2);
  makecopy(n)
}
//判断是否是奇数
bool odd(int n ){
  return n & 1;
}
bool makecopy(int n ){ 
  if(n/2 >1 && odd(n/2))
    copyodd(n);
  else 
    copy(n);
}

void copyodd(int n){
  int m = n/2;
  for (int  i=1; i<=m; i++){
    b[i]=m+i;
    b[m+i]=i; 
  }
   for (int  i=1; i<=m; i++){
    for (int  j=1; j<=m+1; j++){
      if(a[i][j] >m){
        a[i][j] = b[i];
        a[m+i][j] = (b[i]+m) % n ;
      }
      else
        a[m+i][j] = a[i][j] + m;
    }
    for (int  j=1; j<=m; j++){
      a[i][m+j] = b[i+j-1];
      a[b[i+j-1]][m+j] = i;
    }
  }
}

void copy(int n){
  int m=n/2;
  for(int i=1;i<=m;i++){
     for(int j=1;j<=m;i++){
      a[i][j+m]=a[i][j]+m;
      a[i+m][j]=a[i][j+m];
      a[i+m][j+m]=a[i][j];
    }
  }
}

时间复杂度

在进行计算n个运动员比赛顺序时，与在计算，与计算2^k个运动员时所用分治算法基本一样。

参考链接：

https://blog.csdn.net/qq_44116998/article/details/112396925?ops_request_misc=&request_id=&biz_id=102&utm_term=%E5%81%87%E8%AE%BE%E6%9C%89n%E4%B8%AA%E8%BF%90%E5%8A%A8%E5%91%98%E8%A6%81%E8%BF%9B%E8%A1%8C%E7%BD%91%E7%90%83%E5%BE%AA%E7%8E%AF%E8%B5%9B&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-2-112396925.pc_search_result_control_group&spm=1018.2226.3001.4187

题目三：矩阵连乘问题

算法描述

将连乘积,......,简单记作：A[i:j]，其中的维度记作 ∗
若有一个计算 A[1:k]的次序所需的计算量更少，则取而代之，类似，计算 A[k+1:n]的次序也 一定是最优的
同时，矩阵连成计算次序问题的最优解，包含了其子问题的最优解
那么，计算目的是求解 A[1:n]的最优解，而一个最优策略也应是最优的，所以问题可分解为 求 A[i:j]的最小计算次序
考察计算 A[i:j]的最有计算次序：设这个计算次序在矩阵和之间将矩阵链断开，i<=k<=j。 则其相应加括号的方式为：(......)(......)
那么 A[i:j]的计算量为 A[i:k]的计算量加上 A[k+1:j]的计算量，再加上 A[i:k]和 A[k+1,j]相乘的计算量

递归函数

image.png

时间复杂度

循环体内的计算量为 O(1)，循环体为三重循环，所以算法计算时间为 O()