矩阵乘法--Strassen算法
一、矩阵乘法

从中可以看出,计算两个矩阵的乘积,需要三个 for 循环,可以简单写出代码:
for(int i=1;i<=m;i++)for(int j=1;j<=p;j++)for(int k=1;k<=n;k++)c[i][j]+=a[i][k]*b[k][j];
时间复杂度的分析:很明显,三层for循环迭代,复杂度为
二、Straasen 算法
与简单的矩阵乘法计算不同,Strassen算法通过分治操作将运行变快,时间复杂度为
1.Strassen 算法的原理:


简单的计算备用矩阵和式 :通过简单的两层for循环将其加减
备用的乘积: 递归调用strassen算法,因为已逐步构造好分块的A和S矩阵,将需要的矩阵作为strassen的输入,就可以得出P矩阵
最后计算将C矩阵的四个分矩阵求出,再合并求得最后的C矩阵


①矩阵相加减:
void plus(int **matrixa,int **matrixb,int **matrixc, int x) // 矩阵相加
{for(int i=1;i<=x;i++)for(int j=1;j<=x;j++)matrixc[i][j]=matrixa[i][j]+matrixb[i][j];
}
void cut(int **matrixa,int **matrixb,int **matrixc,int x1) // 矩阵相减
{for(int i=1;i<=x1;i++)for(int j=1;j<=x1;j++)matrixc[i][j]=matrixa[i][j]-matrixb[i][j];
}
② 矩阵的拆分(将一个矩阵分成四个小矩阵)与合并:
for(int i=1;i<=newx;i++)
for(int j=1;j<=newx;j++)
{ a11[i][j]=ma[i][j];a12[i][j]=ma[i][j+newx];a21[i][j]=ma[i+newx][j];a22[i][j]=ma[i+newx][j+newx];b11[i][j]=mb[i][j];b12[i][j]=mb[i][j+newx];b21[i][j]=mb[i+newx][j];b22[i][j]=mb[i+newx][j+newx];
}for(int i=1;i<=newx;i++)
for(int j=1;j<=newx;j++)
{mc[i][j]=c11[i][j]; mc[i][j+newx]=c12[i][j];mc[i+newx][j]=c21[i][j];mc[i+newx][j+newx]=c22[i][j];
}
③递归调用过程:
strassen(a11,s1,p1,newx);
strassen(s2,b22,p2,newx);
strassen(s3,b11,p3,newx);
strassen(a22,s4,p4,newx);
strassen(s5,s6,p5,newx);
strassen(s7,s8,p6,newx);
strassen(s9,s10,p7,newx);
2.关于Strassen算法的理解:
Strassen算法的理论推导是比较难的,或者说,是前人不断的试验发现得出的结果,因此需根据得出的公式打出代码。
代码的难度在于很多地方。
①递归的调用:将预处理的代码通过递归计算出。
②二维矩阵的存储以及二维数组在函数中的传递调用:
因为在递归中的数组是反复调用的,所以一定不能使用全局数组导致计算混乱。
另一个是二维矩阵的定义,不能简单定义静态数组,定义静态数组过大程序无法运行,并且运行速度慢,而应当定义malloc动态数组,数组大小可以改变,而且运行时高效很多。
malloc定义二维动态数组:
c=(int **)malloc(sizeof(int *)*n);
for(int i=1;i<=n;i++)c[i]=(int *)malloc(sizeof(int)*n);
三、Strassen 算法的改进
通过上述的理解,可以知道Straasen算法适用于当阶数为 2的幂(或者2的倍数) 时,是否能使其扩大适用范围,让任何相同阶数的矩阵算法都能使用。
当矩阵的阶数为奇数时,只需要将其行列各增加1,并且增加的元素全为0,即可使用 Straasen算法。
改进Strassen算法的复杂度:改进算法并未与原算法发生实质性的改变,因此时间复杂度不发生改变。
相关文章:
矩阵乘法--Strassen算法
一、矩阵乘法 从中可以看出,计算两个矩阵的乘积,需要三个 for 循环,可以简单写出代码: for(int i1;i<m;i)for(int j1;j<p;j)for(int k1;k<n;k)c[i][j]a[i][k]*b[k][j]; 时间复杂度的分析:很明显,…...
Unity笔记:C#基础(1)
杂项 虚函数 CSDN - C虚函数详解 cnblog - C#中的虚函数virtual 常量池与new 在C#中,string是不可变的,这意味着对string对象的操作通常会返回一个新的string对象,而不会修改原始的string对象。因此,几乎所有涉及更改string内…...
计算机科技与心理学的紧密交织:一场跨学科的深度对话
随着信息技术的飞速发展,计算机科学与心理学这两门看似迥异的学科日益呈现出密不可分的关系。本文将深入探讨计算机科学与心理学之间的相互影响和融合,揭示二者在研究方法、应用实践以及对未来社会发展的影响等方面的高度关联性。 计算机科学为心理学研究…...
【JAVA类】利用接口的多继承实现———图书管理系统【附源码】
引言 在我们学习了一些java的基础语法之后,需要把这些知识点可以串起来,这里使用一个简单的小项目可以很好的帮助我们牢记这些知识点,今天就带大家学习一个有关java的小项目,很多学校也经常把这个项目作为他们的课程设计——经典的…...
Linux进程概念僵尸进程孤儿进程
文章目录 一、什么是进程二、进程的状态三、Linux是如何做的?3.1 R状态3.2 S状态3.3 D状态3.4 T状态3.5 t状态3.6 X状态3.7 Z状态 四、僵尸进程4.1 僵尸进程危害 五、孤儿进程 一、什么是进程 对于进程理解来说,在Windows上是也可以观察到的,…...
实体店如何引流成交裂变?打造流量新引擎的秘诀
在数字化浪潮席卷的今天,实体店经营面临着前所未有的挑战与机遇。社区店作为连接居民日常生活的桥梁,如何在激烈的市场竞争中脱颖而出,实现引流、成交与裂变,成为摆在每一位实体店创业者面前的重要课题。 作为一名鲜奶吧开店5年的…...
蓝桥杯(日期问题纯暴力)
纯纯暴力,写的想吐,玛德服了。 但是复习了vector去重方法,日期的合法性判断。 #include <iostream> #include <vector> #include <cstring> #include <algorithm>using namespace std; vector<int> res; st…...
ES: ES+Kibana 环境部署
ESKibana 部署 机器信息 10.10.8.62 10.10.8.63 10.10.8.64版本选择:6.8.1 基础环境优化 所有节点 # 关闭防火墙 systemctl stop firewalld.service systemctl disable firewalld.service# 查看selinux getenforce # 关闭selinux setenforce 0 # 永久关闭se…...
Find My产品越来越得到市场认可,伦茨科技ST17H6x芯片赋能厂家
苹果发布AirTag发布以来,大家都更加注重物品的防丢,苹果的 Find My 就可以查找 iPhone、Mac、AirPods、Apple Watch,如今的Find My已经不单单可以查找苹果的设备,随着第三方设备的加入,将丰富Find My Network的版图。产…...
Linux系统——Haproxy高性能负载均衡软件
目录 一、Haproxy介绍 1.Haproxy定义 2.Haproxy主要特性 二、安装Haproxy 1.yum安装 2.第三方rpm包安装 3.编译安装 3.1解决Lua环境 3.2编译安装Haproxy 三、配置文件详解 1.状态页 2.日志管理 2.1定义日志到其他主机站点 3.指定进程线程个数 4.cpu亲缘性 5.多进…...
Python办公自动化之PDF(二)
Python操作PDF二 1、PyMuPDF简介2、 1、PyMuPDF简介 PyMuPDF(也称Fitz)开源,提供了一整套用于处理PDF文件的综合工具。使用PyMuPDF,用户可以高效地执行打开PDF、提取文本、图像和表格、操作旋转和裁剪等页面属性、创建新PDF文档以…...
登录失败重试次数安全设计方案
1、登录失败重试次数设计方案 1、无论是账号还是密码错误,统一提示:用户名或密码错误,账号剩余登录次数N! 2、同一账号连续登录失败5次,锁定该账号5分钟,5分钟后可以再重试登录。 开发设计 keyÿ…...
Django——模板
Django——模板 Django 提供一种动态生成 HTML 页面 —— 模板 1、模板语言 模板语言(DTL): 变量 , 注释 , 标签 , 过滤器 , 模板继承 1、变量 <body> <!-- 这个是前端中的注释 --> {# 这种是Django中模板语言的…...
角蜥优化算法 (Horned Lizard Optimization Algorithm ,HLOA)求解无人机路径优化
一、无人机路径规划模型介绍 无人机三维路径规划是指在三维空间中为无人机规划一条合理的飞行路径,使其能够安全、高效地完成任务。路径规划是无人机自主飞行的关键技术之一,它可以通过算法和模型来确定无人机的航迹,以避开障碍物、优化飞行时间和节省能量消耗。 二、算法介…...
Windows下 OracleXE_21 数据库的下载与安装
Oracle 数据库的下载与安装 数据库安装包下载数据库安装访问数据库进行测试Navicat连接数据库 1. 数据库安装包的下载 1.1 下载地址 Oracle Database Express Edition | Oracle 中国 1.2 点击“下载 Oracle Database XE”按钮,进去到下载页面(选择对…...
新手如何快速上手学习单片机?
读者朋友能容我,不使博文负真心 新开专栏,期待与诸君共享精彩 个人主页:17_Kevin-CSDN博客 专栏:《单片机》 学习单片机是一个有趣且有挑战性的过程。单片机是一种微控制器,广泛应用于各种电子设备和嵌入式系统中。在这…...
grpc的验证器
简介 在使用grpc库时候 ,很多时候我们需要对反序列化的参数进行校验,代码中有很多参数校验的代码,如果手动实现,会非常繁琐,对于grpc来说,在定义proto的时候使用直接定义参数的限制规则是一种更合理、更优雅的方式,插…...
无法找到concrt140.dll怎么办?concrt140.dll丢失的5种解决方法
在我们使用计算机的时候,偶尔会遭遇一些技术问题,其中一个比较常见的问题就是出现了"丢失concrt140.dll文件"的提示。当我们的电脑告诉我们缺少了concrt140.dll文件时,常常是因为某些程序无法找到这个文件而导致了程序的运行异常。…...
Elasticsearch 分享
一、Elasticsearch 基础介绍 ElasticSearch 是分布式实时搜索、实时分析、实时存储引擎,简称(ES), 成立于2012年,是一家来自荷兰的、开源的大数据搜索、分析服务提供商,为企业提供实时搜索、数据分析服务,…...
cpu masks的初始化
在内核中,有几个位图变量是用作标识cpu数量和状态的,它们分别是: 变量名称用途循环所使用的宏cpu_possible_mask系统中有多少个可以运行的cpu核for_each_possible_cpucpu_present_mask系统中有多少个可处于运行状态的cpu核for_each_present_…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...
