文档章节

矩阵快速幂的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
博文 17
码字总数 12986
作品 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
[Java学习探讨]为什么学Java虚拟机的Java程序员更值钱?

[Java学习探讨]为什么学Java虚拟机的Java程序员更值钱? 曾经的我经常害怕处理与JVM相关的异常,对JVM的配置参数也一无所知,那时候我天真地认为,JVM的出现本身就是想让程序员屏蔽实现细节,...

原创小博客
07/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

mysql在查询结果前加序号

在查询结果前加序号: set @rn=0; select @rn:=@rn+1 as 序号,你查询的结果集

lyle_luo
21分钟前
1
0
webpack 工作原理

暂无内容

agenyun
29分钟前
1
0
iOS返回指定控制器或者关闭自己当前控制器

RT。。。 这种情况其实很常见,比如,从A界面进入B界面在进入C界面,如果返回时,直接从C回到A,怎么做?或者说无限跳转进入BCDEF...XYZ。。。之后直接返回某一个界面,怎么做? 其实这种的有...

RainOrz
30分钟前
1
0
文章收藏

对接口或者方法进行性能测试的工具contiperf: http://www.ltesting.net/ceshi/ceshijishu/xncs/2012/1127/205747.html...

月下狼
35分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部