时间复杂度最低的整数相乘

Mgccl · 发表于 2008-6-27 13:47:44

原帖由 shshsh_0510 于 2008-6-27 13:36 发表
我想可能是 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. 在应用的状态下完全可以当其为一常数.

无心人 · 发表于 2008-6-27 13:55:37

浮点FFT的算法就是$O(nlogn)$的

mathe · 发表于 2008-6-27 13:57:15

原帖由 无心人 于 2008-6-27 13:55 发表
浮点FFT的算法就是$O(nlogn)$的

但是这个计算精度是有限制的，如果用于大整数运算，只能计算一定范围内的整数

无心人 · 发表于 2008-6-27 14:43:25

FNT也是这个复杂度的

mathe · 发表于 2008-6-27 15:00:08

FNT也有同样问题，以来于模数的大小。比如你在p阶有限域上做FNT,那么每个参与计算的数（每位数）就不能超过p.
所以这个算法O(n*log(n))指得是使用O(n*log(n))次p阶域中的运算。

无心人 · 发表于 2008-6-27 15:05:26

楼主提供的论文是单精度计算的复杂度？？？

gxqcn · 发表于 2008-6-27 15:36:27

肯定不是单精度的，要不何需费那大周章？

无心人 · 发表于 2008-6-27 16:00:30

我说的意思是他是否以单精度运算做计算复杂度的基本单位

mathe · 发表于 2008-6-27 16:02:23

是的，当然应该如此。

无心人 · 发表于 2008-6-27 17:17:09

仔细读了？
呵呵

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 时间复杂度最低的整数相乘