专栏首页glm的全栈学习之路C语言程序实践第一周报告(.doc版)

C语言程序实践第一周报告(.doc版)

C语言程序实践第一周报告

矩阵乘方

一种朴素的思想

对于普通类型的求a^n,我们的求法是a*a*a*a....,这样乘以n次,时间复杂度为O(n),对于普通n比较小的我们可以接受,然而当n比较大的时候,计算就慢了,所以我们就去寻找更快捷的计算方法,学过快速幂的同学应该不难想到矩阵的快速幂

例如:我们要求2^8,我们通过当为偶数的时候,a^n=(a*a)^(n/2),当n为奇数时,a^n=a*(a*a)^(n/2)的形式,是不是可以转化为4^4->8^2->64^1,就可以了,2^5的话2*4^2->2*16^1。(把幂化为底数,减少乘法的次数)

其实类似这样的思想不少见,我们不应该感到陌生:

例如著名的秦九昭算法(扯远了,但还是要说一下)

背景:

你怎么算呢?暴力乘,好我们来分析一下时间复杂性的问题,你需要加法运算n次,乘法运算1+2+....+n=n*(n+1)/2次,但我们有一个很简单的优化:秦九昭算法

我们只需要n次乘法运算,n次加法运算就可实现多项式求值时间复杂度为o(n)

其实本质是什么呢?

本质是利用已有的数据,就比如说我已经有了x,我去算x^2就不用两次运算,直接在原有的基础上再乘一个x,其实很多别的算法也是基于这个大思想,例如记忆化搜索,前缀和,差分,线段树懒标记

说回正题,基于这样的思想

矩阵快速幂板子应运而生

Mat pow(Mat x,int y)

{

Mat ans;

for(int i=1;i<=n;i++)

{

for(int j=1;j<=n;j++)

{

i==j?ans.m[i][j]=1:ans.m[i][j]=0;//单位矩阵*任何矩阵=任何矩阵本身 单位矩阵定义:对角线上元素为1,其他为0

}

}

while(y) //矩阵快速幂模板

{

if(y&1)

{

ans=Mul(ans,x);

}

x = Mul(x,x);

y>>=1;

}

return ans;

}

唯一要注意的就是奇数和偶数的差别:奇数多乘一次,偶数则不用

之前程序没过的原因:

第一次:没看题目要求n,b,m按顺序输入

第二次:快速幂最后返回的是ans矩阵而不是x矩阵

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 回忆京都

    glm233
  • 对顶堆求区间k小(大)数

    首先,这道题让我们求每次的第i大值,而i是会移动的——那我们就可以理解为,我们需要知道第i大值和第i+1大值(请撕烤)。那用什么数据结构呢?

    glm233
  • xmuC语言程序实践week 1 大作业

      给定一个矩阵A,一个非负整数b和一个正整数m,求A的b次方除m的余数。   其中一个nxn的矩阵除m的余数得到的仍是一个nxn的矩阵,这个矩阵的每一个...

    glm233
  • Java获取随机数的3种方法

    方法1  (数据类型)(最小值+Math.random()*(最大值-最小值+1)) 例:

    ydymz
  • 1.1 可视化概述

    学习PowerBI有三大独立的模块,Power Query获取数据、Power Pivot & DAX 数据建模、Power View 数据可视化,以可视化作为...

    公众号PowerBI大师
  • 开发者自述:我是怎样理解支持向量机(SVM)与神经网络的

    SVM与神经网络 支持向量机并不是神经网络,这两个完全是两条不一样的路吧。不过详细来说,线性SVM的计算部分就像一个单层的神经网络一样,而非线性SVM就完全...

    AI研习社
  • BAT面试题1:请简要介绍下SVM

    接下来,每天推送1道BAT的面试题,一般问到的这些知识点都是很重要的,所以知道的呢就再复习一下,不知道的赶紧弥补。日积月累,你会在不知不觉中就已入机器学习的大门...

    double
  • 如何理解SVM | 支持向量机之我见

    囫囵吞枣看完SVM,个人感觉如果不好好理解一些概念,或说如果知其然而不知其所以然的话,不如不看。因此我想随便写一写,把整个思路简单地整理一遍。:) SVM与神经...

    用户1332428
  • View详解(3)

    大家教师节快乐啊,不知道勤学的Coder们有没有去尝试下绘制上篇文章中最后留下的进阶效果,不管怎样,还是一起动手写一遍吧!看看套路是否一致。

    小海编码日记
  • 资源 | 整合全部顶尖目标检测算法:FAIR开源Detectron

    机器之心

扫码关注云+社区

领取腾讯云代金券