用Strassen算法(分治)计算矩阵乘法及python实现(一)

前言:

设A和B都是n*n的矩阵,那么我们可以很容易通过一个简单的分治算法得到乘积C=A·B,以下是其伪代码,它将接收n*n矩阵A,B,并返回它们的乘积C:

SQUARE-MATRIX-MULLTIPLY(A,B)
n=A.rows
let C be a new n*n matrix
for i=1 to n
     for j=1 to n
         c[i][j]=0
         for k=1 to n
               c[i][j]=c[i][j]+a[i][k]*b[k][j]

return C

显然三重循环中每一重都要执行n布,因此其时间复杂度为O(n^3),而Strassen算法的时间复杂度为O(n^log7),显然Strassen算法更优。

Strassen算法的核心思想是通过常数次的额外的矩阵加法来减少递归的次数,如果你对递归有所了解,那么你应该明白这种代价确实能够减少渐进运行时间。下面来介绍一下Strassen算法的步骤

Strassen算法的步骤

为简单起见,当使用分治算法计算矩阵积C=A*B时,假定三个矩阵均为n*n矩阵,其中n为2的幂。我们做出这个假设是因为在每个分解步骤中,n*n矩阵都被划分为4个n/2*n/2的子矩阵,如果假定n是2的幂,则只要n>=2即可保证子矩阵规模n/2为整数。

Strassen算法一共4个步骤:

  1. 将输入矩阵A、B和输出矩阵C分解为n/2*n/2的子矩阵。采用下标计算方法,此步骤花费O(1)时间。
  2. 创建10个n/2*n/2的矩阵S1, S2, … , S10,每个矩阵保存步骤1中创建的两个子矩阵的和或差。花费时间为O(n^2)。
  3. 用步骤1中创建的子矩阵和步骤2中创建的10个矩阵,递归地计算7个矩阵积P1, P2, …, P7。每个矩阵Pi都是n/2*n/2的。
  4. 通过Pi矩阵的不同组合进行加减计算,计算出结果矩阵C的子矩阵C11, C12, C21, C22。花费时间O(n^2)。

以上即为Strassen算法的简略步骤,至于具体步骤,敬请期待 用Strassen算法(分治)计算矩阵乘法及python实现(二)。

 

浙大版《C语言程序设计(第3版)》题目集

习题10-4 递归求简单交错幂级数的部分和 (15 分)

本题要求实现一个函数,计算下列简单交错幂级数的部分和:

f(x,n)=xx2+x3x4++(1)n1xn

函数接口定义:

double fn( double x, int n );

其中题目保证传入的n是正整数,并且输入输出都在双精度范围内。函数fn应返回上述级数的部分和。建议尝试用递归实现。

裁判测试程序样例:

#include <stdio.h>

double fn( double x, int n );

int main()
{
    double x;
    int n;

    scanf("%lf %d", &x, &n);
    printf("%.2f\n", fn(x,n));

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例:

0.5 12

输出样例:

0.33
double fn( double x, int n )
{	
	if(n==1)
		return x;
	else
		return x-x*fn(x,n-1);
}

 

浙大版《C语言程序设计(第3版)》题目集

习题10-2 递归求阶乘和 (15 分)

本题要求实现一个计算非负整数阶乘的简单函数,并利用该函数求 1!+2!+3!+…+n! 的值。

函数接口定义:

double fact( int n );
double factsum( int n );

函数fact应返回n的阶乘,建议用递归实现。函数factsum应返回 1!+2!+…+n! 的值。题目保证输入输出在双精度范围内。

裁判测试程序样例:

#include <stdio.h>

double fact( int n );
double factsum( int n );

int main()
{
    int n;

    scanf("%d",&n);
    printf("fact(%d) = %.0f\n", n, fact(n));
    printf("sum = %.0f\n", factsum(n));
		
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例1:

10

输出样例1:

fact(10) = 3628800
sum = 4037913

输入样例2:

0

输出样例2:

fact(0) = 1
sum = 0
double fact( int n )
{
	double result;

	if(n==1||n==0)
		result=1;
	else
		result=n*fact(n-1);
	return result;
}
double factsum( int n )
{
	double sum=0;
			
	for(int i=1;i<=n;i++)
	{
		sum+=fact(i);
	}
	return sum;
}