文档章节

矩阵快速幂的JAVA实现

旺仔没馒头
 旺仔没馒头
发布于 2017/09/03 16:14
字数 421
阅读 6
收藏 0

矩阵快速幂

题目描述:

给定一个n*n的矩阵,求该矩阵的k次幂,即P^k。

如何快速的算出一个矩阵的N次幂呢,举个例子,比如A^19 => (A^16)*(A^2)*(A^1)显然采取这样的方式计算时因子数将是log(n)级别的(原来的因子数是n),不仅这样,因子间也是存在某种联系的。 比如A^4能通过(A^2)*(A^2)得到,A^8又能通过(A^4)*(A^4)得到,这点也充分利用了现有的结果作为有利条件。 下面举个例子进行说明:现在要求A^156,而156(10)=10011100(2) 也就有A^156=>(A^4)*(A^8)*(A^16)*(A^128) 考虑到因子间的联系,我们从二进制10011100中的最右端开始计算到最左端。
以下代码就是其实现方式:

public class MatrixMulti {

    public static long[][] mut(int k,int n,long[][] A){
        long [][] res = new long[n][n];
        for(int i = 0 ; i < res.length ;i++){
            for(int j = 0 ; j< res[i].length ;j++){
                if(i==j){
                    res[i][j] = 1;
                }else{
                    res[i][j] = 0;
                }
            }
        }
        while(k!=0){
            if((k&1)==1) res = f(res,A);
            k>>=1;
            A = f(A,A);
        }
        return res;
    }
    public static long[][] f(long[][] A,long[][] B){
        long res[][] = new long[A.length][B.length];
        for(int i = 0 ; i < res.length ;i++){
            for(int j = 0 ; j< res[i].length ;j++){
                for(int k = 0 ; k < A[0].length ;k++){
                    res[i][j] += A[i][k]*B[k][j];
                }
            }
        }
        return res;
    }

}

其中函数f(),是定义了矩阵的乘法运算,在矩阵中,单位矩阵就是相当于常数1,在函数mut()中,最主要的就是while循环里的代码,运用了分治的思想,快速的计算矩阵的n次幂。

© 著作权归作者所有

共有 人打赏支持
上一篇: 串的处理
下一篇: 桥接模式学习
旺仔没馒头
粉丝 2
博文 18
码字总数 13798
作品 0
济南
程序员
私信 提问
Effective Java 第三版——47. 优先使用Collection而不是Stream来作为方法的返回类型

Tips 《Effective Java, Third Edition》一书英文版已经出版,这本书的第二版想必很多人都读过,号称Java四大名著之一,不过第二版2009年出版,到现在已经将近8年的时间,但随着Java 6,7,8...

M104
09/30
0
0
JAVA 持有对象——容器初探

引言 如果一个程序只包含固定数量的且其生命周期都是已知对象,那么这是一个非常简单的程序——《think in java》 了解容器前,先提出一个问题,ArrayList和LinkedList谁的处理速度更快呢? ...

jiangmitiao
2015/08/01
0
2
Python才是人工智能AI的首选编程语言,你值得拥有……

在所有编程语言里,Python并不算萌新,从1991年发布第一个版本,至今已经快30年了。 最近几年,随着人工智能概念的火爆,Python迅速升温,成为众多AI从业者的首选语言。 根据数据平台 Kaggle...

M耀文
05/19
0
0
使用Mahout搭建推荐系统之入门篇4-Mahout实战

用意: 结合上篇博客,写写代码熟悉一下Mahout。很多地方想法都比较粗糙,亟待指正。 代码放在了:https://github.com/xiaoqiangkx/qingRS 一、基本内容 1. 加载数据: 判断userID和itemID的大...

清风漫步
2014/02/21
0
1
HashMap与Hashtable的区别是面试中经常遇到的一个问题。这个问题看似简单,但如果深究进去,也能了解到不少知识。本文对两者从来源、特性、算法等多个方面进行对比总结。力争多角度、全方位的展示二者的不同,做到此问题的终结版。

HashMap与Hashtable的区别是面试中经常遇到的一个问题。这个问题看似简单,但如果深究进去,也能了解到不少知识。本文对两者从来源,特性,算法等多个方面进行对比总结。力争多角度,全方位的...

黑泽明军
04/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

手写tomcat+servlet

写程序一定要有思路,思路很重要! 一、我们分两步第一步先实现手写tomcat,第二部写servlet 所用技术: 1、soket通信 IO流 2、http请求与相应 3、解析xml 4、java反射技术 导入所需要的jar...

jason_kiss
29分钟前
1
0
Beetl模板的基础用法 【变量、循环、条件】---《Beetl视频课程》(2)

本期视频做了一个博客的首页列表; 内容简介:springboot 集成 beetlsql;使用for循环,使用if控制语句,使用虚拟属性,定义变量等等 一起学beetl目录:https://my.oschina.net/u/1590490?ta...

Gavin-King
34分钟前
1
0
各种视频监控上墙方案的比较

方案1、一使用 DVR 、NVR 直接显示上墙 不得不说,这种办法是成本最低廉的,但这里有不少限制: 无法实现分散点的集中上墙。譬如连锁经营的酒店,如果我在总部建立一个集中上墙的环境,这个就...

PeakFang-BOK
58分钟前
4
0
netfilter 和 iptables

一. netfilter 1. 什么是entfilter 和 iptables netfilter指整个项目名 在这个项目里面,netfilter特指内核中的netfilter框架, iptables指用户空间的配置工具。 netfilter在协议栈中添加了5...

Fc丶
今天
2
0
搞定了微信小程序富文本渲染解决方案-后端渲染方案Html2Wxml2J

先介绍一下最近遇到的问题: 最近小程序项目中有文章详情页需要渲染富文本,微信小程序官方提供的<rich-text>是个弱鸡,很多标签不支持,用起来也麻烦,性能也不咋地。 吐槽完了,我们决定寻...

山东-小木
今天
32
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部