文档章节

矩阵快速幂的JAVA实现

旺仔没馒头
 旺仔没馒头
发布于 2017/09/03 16:14
字数 421
阅读 5
收藏 0
点赞 0
评论 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
博文 15
码字总数 10924
作品 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
HashMap与Hashtable的区别是面试中经常遇到的一个问题。这个问题看似简单,但如果深究进去,也能了解到不少知识。本文对两者从来源、特性、算法等多个方面进行对比总结。力争多角度、全方位的展示二者的不同,做到此问题的终结版。

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

黑泽明军
04/07
0
0
使用Mahout搭建推荐系统之入门篇4-Mahout实战

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

清风漫步
2014/02/21
0
1
Java程序员必读书单,家族又添新成员

点击关注异步图书,置顶公众号 每天与你分享IT好书 技术干货 职场知识 参与文末话题讨论,每日赠送异步图书。 ——异步小编 有些革命出其不意地吸引了全世界的眼球。Twitter、Linux操作系统和...

异步社区
05/09
0
0
ThreadLocal源码分析

阅读原文请访问我的博客 BrightLoong's Blog 一. 简介 提醒篇幅较大需耐心。 简介来自ThreadLocal类注释 ThreadLocal类提供了线程局部 (thread-local) 变量。这些变量与普通变量不同,每个线...

BrightLoong
05/28
0
0
Java开发学习之三版本简介 java编程

  Java编程语言,在更迭迅速的互联网领域多年屹立不倒,足以得见Java这门语言旺盛的生命力,因此,会有很多想要进入互联网领域的朋友,想要学Java来转行开发。但是,所谓“隔行如隔山”,j...

老男孩Linux培训
06/05
0
0
LeetCode:Set Matrix Zeroes - 将矩阵内含有零的行和列全部置零

1、题目名称 Set Matrix Zeroes(将矩阵内含有零的行和列全部置零) 2、题目地址 https://leetcode.com/problems/set-matrix-zeroes/ 3、题目内容 英文:Given a m x n matrix, if an eleme...

北风其凉
2015/11/07
0
0
Google 正式开源 Jib ,帮助 Java 应用快速容器化

Google 本周宣布开源一款新的 Java 工具 Jib ,旨在让开发者使用他们熟悉的工具更轻松地将 Java 应用程序容器化。 在7月9日发布的博客文章中,Google 软件工程师 Appu Goundan 和 Qingyang C...

王练
07/11
0
0
伪共享和缓存行填充,Java并发编程还能这么优化!

前言 关于伪共享的文章已经很多了,对于多线程编程来说,特别是多线程处理列表和数组的时候,要非常注意伪共享的问题。否则不仅无法发挥多线程的优势,还可能比单线程性能还差。随着JAVA版本...

技术小能手
07/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Confluence 6 配置时间和日期格式

你可以修改你 Confluence 为用户显示的时期和时间格式。设置的句法使用的是 SimpleDateFormat class,请参考 Java SimpleDateFormat 文档中的内容来设置日期和时间格式。 有下面 3 个时间和日...

honeymose
9分钟前
0
0
php seralize unserialize

关于PHP 序列化(serialize)和反序列化(unserialize)出现错误(Error at offset)的解决办法。 首先我们分析一下为什么会出现这个错误: 编码问题 UTF-8: ANSI: 我发现在我的机器上边编码改...

yeahlife
16分钟前
0
0
七、JSP九大内置对象和四个作用域

九大内置对象: request:类型是HttpServletRequest,和Servlet里的HttpServletRequest一模一样。 response:类型是HttpServletResponse,和Servlet里的HttpServletResponse一模一样。JSP里基...

Wakeeee_
19分钟前
0
0
第十四章NFS服务搭建与配置

14.1 NFS介绍 NFS介绍 NFS是Network File System的缩写;这个文件系统是基于网路层面,通过网络层面实现数据同步 NFS最早由Sun公司开发,分2,3,4三个版本,2和3由Sun起草开发,4.0开始Netap...

Linux学习笔记
51分钟前
0
0
双向认证-nginx

1、设置容器 docker run -it --name nginx-test2 -v /home/nginx:/apps -v /home/nginx/conf/nginx.conf:/etc/nginx/nginx.conf:ro -p 8183:80 -p 7443:443 -d nginx:stable 2、修改nginx配......

hotsmile
52分钟前
0
0
深入了解 Java 自动内存管理机制及性能优化

一图带你看完本文 一、运行时数据区域 首先来看看Java虚拟机所管理的内存包括哪些区域,就像我们要了解一个房子,我们得先知道这个房子大体构造。根据《Java虚拟机规范(Java SE 7 版)》的规...

Java大蜗牛
54分钟前
4
0
SpringBoot | 第六章:常用注解介绍及简单使用

前言 之前几个章节,大部分都是算介绍springboot的一些外围配置,比如日志 配置等。这章节开始,开始总结一些关于springboot的综合开发的知识点。由于SpringBoot本身是基于Spring和SpringMvc...

oKong
54分钟前
9
0
云数据库架构演进与实践

如今,大型企业如金融企业和银行等,在下一代的微服务架构转型要求下,需要基础软件和数据平台能够实现原生的云化,以满足微服务架构的需求。 微服务,也就是一种面向服务的,有特定边界的松...

巨杉数据库
55分钟前
0
0
Linux系统梳理---系统搭建(一):jdk卸载与安装

1.去官网下载符合Linux版本的jdk,暂用jdk-8u171-linux-x64.rpm 2.登陆Linux,进入usr目录,创建java目录(方便管理,可以其他位置):mkdir java 3.上传下载的jdk包至Linux服务器,使用rz指令(sz f...

勤奋的蚂蚁
今天
0
0
Linux Kernel 4.16 系列停止维护,用户应升级至 4.17

知名 Linux 内核维护人员兼开发人员 Greg Kroah-Hartman 近日在发布 4.16.18 版本的同时,宣布这是 4.16 系列的最后一个维护版本,强烈建议用户立即升级至 4.17 系列。 Linux 4.16 于 2018 年...

六库科技
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部