从离散卷积到快速傅里叶变换——FFT
前言今天刚好看到3Blue1Brown的卷积视频视频然后看到做卷积的快速算法涉及到了FFT,于是就研究了半天FFT到底是什么引入首先说明一下卷积是在做什么,3B1B这个视频主要是讲解了离散卷积以这个色子概率问题为例子,两个色子的点数之和的求解就可以表示成卷积的形式将一行色子倒序,然后与另一行色子进行一个类似滑动窗口匹配的形式,便可以计算卷积的结果,事实上其实就是如同上图的这样一个公式。这便是...
前言今天刚好看到3Blue1Brown的卷积视频视频然后看到做卷积的快速算法涉及到了FFT,于是就研究了半天FFT到底是什么引入首先说明一下卷积是在做什么,3B1B这个视频主要是讲解了离散卷积以这个色子概率问题为例子,两个色子的点数之和的求解就可以表示成卷积的形式将一行色子倒序,然后与另一行色子进行一个类似滑动窗口匹配的形式,便可以计算卷积的结果,事实上其实就是如同上图的这样一个公式。这便是...
适用场景树状数组是一种适用于多次单点修改统计区间和问题的数据结构。基本思想Binary Indexed Tree 求和的基本思想在于,给定需要求和的位置 ...
应用程序基本执行环境在这种执行环境下,操作系统与应用程序的界限并不明显,应用程序即是操作系统的组成部分,均在内核态下运行,一旦应用程序出错,便会导致整个操作系统的崩溃批处理操作系统从批处理操作系统开始,用户程序与操作系统有了明显的界限,用户程序运行在用户态下,对于一些操作需要通过特权级的切换来完成(系统调用),这时,在操作系统与用户程序间建立了系统调用接口(syscall)。通过这种方式,也...
在这里,我们把有序数组定义为 nums,n 是该数组的长度。搜索某一元素的左边界int l = 0, r = nums.size(); // 找左边界 w...
从汇编语言的视角来看在函数调用的时候,需要有一条指令跳转到被调用函数的位置,这个看起来和其他控制结构没什么不同;但是在被调用函数返回的时候,我们却需要返回那条跳转过来的指令的下一条继续执行。这次用来返回的跳转究竟跳转到何处,在对应的函数调用发生之前是不知道的。比如,我们在两个不同的地方调用同一个函数,显然函数返回之后会回到不同的地址。这是一个很大的不同:其他控制流都只需要跳转到一个 编译期固...