Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform

Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
复制标题

关于快速傅立叶变换线性复杂度下界的注记

DOI：
--
复制
发表时间：
1973
期刊：
JACM
影响因子：
--
通讯作者：
Jacques Morgenstern
Jacques Morgenstern
中科院分区：
--
文献类型：
--
作者：
Jacques Morgenstern

文献摘要

被引文献

相似文献

当一个上界&lt；italic&gt；/italic&gt；可以赋给计算中所涉及的复数的模时，给出了用线性算法计算一族线性函数族所需的加法次数的下界。在快速傅立叶变换的情况下，当&lt；italic&gt；c&lt；/italic&gt；=1时，下限为(&lt；italic&gt；n&lt；/italic&gt；/italic&gt；/log&lt；subscrpt&gt；2&lt；/subscrpt&gt；&lt；italic&gt；n&lt；/italic&gt；)。
A lower bound for the number of additions necessary to compute a family of linear functions by a linear algorithm is given when an upper bound <italic>c</italic> can be assigned to the modulus of the complex numbers involved in the computation. In the case of the fast Fourier transform, the lower bound is (<italic>n</italic>/2) log<subscrpt>2</subscrpt><italic>n</italic> when <italic>c</italic> = 1.