发布于

动态规划的斜率优化

在某些情况下, 动态规划的转移数目过多导致即使使用动态规划算法也会令复杂度过高. 但往往, 在某些情况下状态转移方程具有某些特别的性质, 对转移方程进行变形就可以转化为某种斜率的形式, 利用斜率的几何意义构造凸集, 通过维护一个单调双端队列使得​\( O(n^2) \)​复杂度的状态转移优化至​\( O(n) \)​.

下面结合几个例子讲一讲。

继续阅读“动态规划的斜率优化”
发布于

VOCALOID学习日志（0）——相关软件的下载与安装（正版获取）

说到Vocaloid的相关教程，梦尘脑子里已经构思好了后续文章的想法思路，结果发现貌似想要拉萌新入坑，除了用人设让他们爱上这些可爱的妹子们，更要让他们产生调教的欲望（笑）。

所以，如果萌新们想要成为一名调教师的话，手里面总要有些工具的嘛。（虽然自己也是萌新）

嘛，于是就在这里先介绍相关软件的下载与安装方法（大量链接警告！！！）

继续阅读“VOCALOID学习日志（0）——相关软件的下载与安装（正版获取）”

发布于

矩阵乘法的strassen算法

直接按照定义计算两个n阶实数方阵的乘积需要进行​\( n^3 \)​次实数乘法

如果将方阵分割，按照矩阵的分块乘法去计算，看似通过递归化简了问题，实际上完成乘法的复杂度依然是​\( \Theta (n^3) \)​。因为矩阵分块之后分治为了八次小矩阵乘法，然后进行矩阵加法，递推式 \(T(n) = 8T(\frac{n}{2}) + \Theta(n2)\)给出的这种方法的解，依然是\( \Theta (n^3) \)

而strassen算法给出了一个复杂度为​\( \Theta (n^{\log _{2} 7}) \)​\( \approx\Theta( n^{2.81}) \)的算法

继续阅读“矩阵乘法的strassen算法”