算法分析第六章 基本算法设计策略 分治法.ppt

VI基本算法设计策略;基本策略;6.1分治法 ; 从而仅需3次乘法即可完成 ? 该算法即STARSSEN矩阵乘法的来源 ;2FFT?该变换的逆变换为 令 则上式可写为 其它的一个重要性质时域卷积对应于频域积 ;多项式的积 两个多项式的积 其中 此即卷积运算 ; 序列运算可用蝶形表示 对于以下的8个的情形 这一描述复杂并且不直观 ;这一变换基于运算中的性质 从算法分析角度 于是分别考虑对其奇数项和偶