算法问题-矩阵乘法，循环赛日程表，矩阵连乘

2021-10-10 本文已影响0人吃核桃用手夹

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

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

算法描述

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

时间复杂度分析

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

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

算法描述

当选手n为 $2^k$ 时，每次递归计算 $2^{k-1}$ 个选手，将左上角递归算出的小块中所有数字按其相对位置抄到右下角，将左上角所有数字加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个运动员时所用分治算法基本一样。
$T(n)=\left\{ \begin{aligned} O(1) && n=1,2\\ 2T(n/2) + O(1) && n>2 \\ \end{aligned} \right.$

参考链接：

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