首页 > Python资料 博客日记
稀疏矩阵的快速转置
2024-08-18 00:00:15Python资料围观34次
这篇文章介绍了稀疏矩阵的快速转置,分享给大家做个参考,收藏Python资料网收获更多编程知识
首先,我们使用三元组来描述稀疏矩阵,三元组包含矩阵元素的位置信息和元素值。使用三元组表来描述所有的非0元素。
然后,转置指的是将矩阵第i行第j列的元素调整到第j行第i列上。
一、一般的转置算法
一般的转置算法是首先遍历三元组表A,找到列数为0的元素,依次转置到B中。
然后,再次遍历遍历三元组表A,找到列数为1的元素,依次转置到B中。
遍历三元组表A,找到列数为2的元素,依次转置到B中。
.。。。
遍历三元组表A,找到列数为n-1的元素,依次转置到B中。
经过这样的遍历,算法时间复杂度为O(t*n)。 t为三元组个数,n为矩阵列数。
二、稀疏矩阵快速转置
那么,快速转置到底快在什么地方呢?
它通过找到一些规律,从而不需要多次遍历三元组表,只需要遍历一次三元组表就能将每一个元素转置成功,但它额外利用了辅助数组,因此它是以空间换时间。所以时间复杂度为O(n+t)。扫描三元组表是O(t),初始化数组是O(n)。所以时间复杂度是O(n+t)。
它找到的是什么规律呢?
1.转置前元素列号j就是转置后元素的行号
2.第j列中第一个非零元素在转置矩阵中的存储位置为:前j列元素的个数之和
有了以上两点发现后,就可以实现快速转置了。
num[]数组用来记录每一列的非零元素个数,k[j]数组计算前j列元素的个数和。
这样,每一列的第一个非0元素就可以填入自己的位置,k[j]数组进行+1操作,为本列其他非0元素提供存储的位置下标。
版权声明:本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!
标签:
相关文章
最新发布
- 【Python系列】SQLAlchemy 基本介绍
- 【Python】selenium 的EC.presence_of_element_located 和 EC.element_to_be_clickable 的区别
- 从零到一!超详细Pycharm安装教程(图解+详细步骤)
- python json jsonl 的用法
- 【Python篇】深度探索NumPy(下篇):从科学计算到机器学习的高效实战技巧
- boto3:Python连接S3对象存储并进行文件操作(上传、下载、删除)
- 全网最适合入门的面向对象编程教程:50 Python函数方法与接口-接口和抽象基类
- Python pycryptodome类库使用学习总结
- import torch 报错:WinError 126
- 如何在Java中实现邮件发送功能?
点击排行
- 版本匹配指南:Numpy版本和Python版本的对应关系
- Python 可视化 web 神器:streamlit、Gradio、dash、nicegui;低代码 Python Web 框架:PyWebIO
- 版本匹配指南:PyTorch版本、torchvision 版本和Python版本的对应关系
- 相关性分析——Pearson相关系数+热力图(附data和Python完整代码)
- Could not build wheels for llama-cpp-python, which is required to install pyproject.toml-based proj
- Python pyinstaller打包exe最完整教程
- Anaconda版本和Python版本对应关系(持续更新...)
- Python与PyTorch的版本对应