零基础学算法100天第7天——二维差分(差分矩阵)(上)

简介: 零基础学算法100天第7天——二维差分(差分矩阵)

1、什么是差分矩阵?


 二维差分我们通常称之为差分矩阵。通过结合一维差分我们可以想到,它的作用是可以让某个子矩阵在O(1)的时间复杂度内让所有元素都加上c。


 而我之前一直都在强调一点——前缀和与差分是逆运用,二维亦是如此。


 如果我们有了一个b[][]如图:


image.png


很明显它的二维前缀和数组a[][]应该为:


image.png


 两者的关系为——a 是 b 的 前 缀 和 数 组 , 而 b 是 a 的 差 分 数 组 ( 差 分 矩 阵 ) a是b的前缀和数组,而b是a的差分数组(差分矩阵)a是b的前缀和数组,而b是a的差分数组(差分矩阵)


2、差分矩阵的核心操作


 我们前面已经提过,差分矩阵b[][]是帮助我们在O(1)时间内让原数组a[][]的某个子矩阵加上c。类似二维前缀和的讲解,通过图解能最快速帮忙大家理解差分矩阵的核心操作 :


 1、首先我们有一个如图的数组a[][] ,我们想让红色板块的值都加上c


 image.png


 2、如果我们此时对数组b[][]的该点加上c


 image.png


 3、因为a[][]是b[][]的前缀和数组,根据二维前缀和的初始化出发,会使得a[][]以下子矩阵全部都加上c


 image.png


 4、很显然,增加的面积超出了我们想要的范围,所以我们还需要减去a[][]中这两个子矩阵的面积


 image.png


image.png   

 5、又可以很明显的发现,减去的这两个子矩阵有重合的地方,我们多减了一次,最后还需要加回来,对于这两个减去子矩阵以及加回多减的操作。我们只需要让b[][]的绿色两点减上c,红色点加上c

 

image.png

相关文章
|
10天前
|
机器学习/深度学习 传感器 算法
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
97 14
|
15天前
|
机器学习/深度学习 边缘计算 分布式计算
基于差分进化算法的微电网调度研究(Matlab代码实现)
基于差分进化算法的微电网调度研究(Matlab代码实现)
|
4月前
|
机器学习/深度学习 算法
基于差分进化灰狼混合优化的SVM(DE-GWO-SVM)数据预测算法matlab仿真
本项目实现基于差分进化灰狼混合优化的SVM(DE-GWO-SVM)数据预测算法的MATLAB仿真,对比SVM和GWO-SVM性能。算法结合差分进化(DE)与灰狼优化(GWO),优化SVM参数以提升复杂高维数据预测能力。核心流程包括DE生成新种群、GWO更新位置,迭代直至满足终止条件,选出最优参数组合。适用于分类、回归等任务,显著提高模型效率与准确性,运行环境为MATLAB 2022A。
|
7月前
|
机器学习/深度学习 算法 机器人
强化学习:时间差分(TD)(SARSA算法和Q-Learning算法)(看不懂算我输专栏)——手把手教你入门强化学习(六)
本文介绍了时间差分法(TD)中的两种经典算法:SARSA和Q-Learning。二者均为无模型强化学习方法,通过与环境交互估算动作价值函数。SARSA是On-Policy算法,采用ε-greedy策略进行动作选择和评估;而Q-Learning为Off-Policy算法,评估时选取下一状态中估值最大的动作。相比动态规划和蒙特卡洛方法,TD算法结合了自举更新与样本更新的优势,实现边行动边学习。文章通过生动的例子解释了两者的差异,并提供了伪代码帮助理解。
434 2
|
10月前
|
算法
|
12月前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
12月前
|
机器学习/深度学习 算法 搜索推荐
django调用矩阵分解推荐算法模型做推荐系统
django调用矩阵分解推荐算法模型做推荐系统
162 4
|
人工智能 算法 JavaScript
【算法】前缀和与差分
算法学习——前缀和与差分(含一维和二维)
156 4
【算法】前缀和与差分
|
12月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
747 0
|
12月前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)

热门文章

最新文章