复习南开大学软件学院2021年秋季学期研究生算法课程贪心分治之分治（包含快速 _算法

状态空间中的算法状态空间：状态（点）+状态转移（边）+价值函数（点权）分治：子问题互不重叠，但最优子结构需考虑全部子问题贪心：子问题互不重叠，但最优子结构仅考虑极少子问题
若认为动态规划算法的状态空间是有向无环图的话，对于分治和贪心，其状态空间通常可以建模成树，分治需要评估整个树，贪心则是树上的几条链
分治与贪心经典算法回顾归并排序：用两个子状态的解构造按序拼接当前状态的解，分治算法，时间复杂度O(n logn) 逆序对个数：用两个子状态的解构造统计个数当前状态的解，分治算法，时间复杂度O(n logn) 快速排序：需用两个子状态的解构造按序拼接当前状态的解，分治算法，期望时间复杂度O(n logn) 第k大数：仅需某一个子状态的解即可，贪心算法，期望时间复杂度O(n) 矩阵快速幂：两个子状态的解相同，贪心算法，时间复杂度O(logn) 分治矩阵乘法
给出矩阵
，求
。
算法会复用分块矩阵乘法结果，先10次加法计算：再用7次乘法计算：最终使用8次加法得出结果：时间复杂度？
分治算法的时间复杂度：T(n)=aT(n/b)+O(n^d) 主定理一维数值积分
给出一维函数
，计算
(无闭式解)
求过2个点的线性函数
即线性插值（一次插值）一维数值积分
给出一维函数
，计算
(无闭式解)
梯形法即为一次插值（但是近似程度不够）优化一：利用二次插值（利用a，m=(a+b)/2，b三个点）一维数值积分
给出一维函数
，计算
(无闭式解)
计算S(a,m,f)和S(m,b,f)若

文章插图
，则返回S(a,b,f)否则，返回
时间复杂度？取决于
的性质和
的大小思考：高维积分这种方法还可行吗？不可行的话该怎么办？多项式算法
n阶多项式A(x)的定义为
给出两个n阶多项式A(x)，B(x)，计算C(x)=A(x)?B(x)
多项式的表示法
以下对n-1阶多项式
讨论
点值表示法Point-value多项式表示法的转换
以下对n-1阶多项式
讨论
插值：点值表示?插值表示
于是，计算乘积
可以通过
快速傅里叶变换Fast，FFT
选n个特殊点
，用分治优化求值和插值为O(n logn)
特殊的点
为第k个n次单位根
背景知识：复变函数
n个单位根构成了循环群，生成元（本源根）

文章插图
模n加/乘法群，
，
折半引理：
消去引理：
求和引理：
离散傅里叶变换，DFT
即对n-1阶多项式A(x)在n次单位根上的求值过程
在这种情况下，向量
即为系数向量
的离散傅里叶变换，记作由单位根
的特殊性质，DFT可用分治快速完成?FFT 快速傅里叶变化（求值部分）由此可得分治算法的关键：
因此，计算A(x)在
上的值，可以转化为：
具体来说，计算
【复习南开大学软件学院2021年秋季学期研究生算法课程贪心分治之分治（包含快速】，可以转化为：总结来说，A(x)上的n次单位根的值，只需分别计算一遍
，
的n/2次单位根值即可构造出来时间复杂度？
快速傅里叶变换（插值部分）分治算法小结子问题规模要成倍缩小；（分解）假设子问题完成，如何得出原问题的答案；（合并）

复习 南开大学软件学院2021年秋季学期研究生算法课程贪心分治之分治（包含快速

复习南开大学软件学院2021年秋季学期研究生算法课程贪心分治之分治（包含快速