原帖由 shshsh_0510 于 2008-6-27 13:36 发表 http://bbs.emath.ac.cn/images/common/back.gif
我想可能是lglglg...lgn 的意思
对, 麻省理工出版社的Introduction To Algorithm(算法导论)page 56上面的定义. 叫做iterated logrithm.
首先定义function iteration
$f^{(i)}(x) = f(f(f(f(f(f....(x))))))$ f(x)自己的结果i次.
$lg**n = min{i>=0: lg^{(i)} n <=1}$
lg*(2^65536) = 5.
现在应用的计算不可能做到lg*(x) = 6. 在应用的状态下完全可以当其为一常数.
浮点FFT的算法就是$O(nlogn)$的
原帖由 无心人 于 2008-6-27 13:55 发表 http://bbs.emath.ac.cn/images/common/back.gif
浮点FFT的算法就是$O(nlogn)$的
但是这个计算精度是有限制的，如果用于大整数运算，只能计算一定范围内的整数
FNT也是这个复杂度的
FNT也有同样问题，以来于模数的大小。比如你在p阶有限域上做FNT,那么每个参与计算的数（每位数）就不能超过p.
所以这个算法O(n*log(n))指得是使用O(n*log(n))次p阶域中的运算。
楼主提供的论文是单精度计算的复杂度？？？
肯定不是单精度的，要不何需费那大周章？
:lol
我说的意思是他是否以单精度运算做计算复杂度的基本单位
是的，当然应该如此。
仔细读了？
呵呵