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

Mgccl · 发表于 2008-6-27 12:11:19

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

专门发一个帖子,记录时间复杂度最低的整数相乘...
2007年Martin Fürer 发现的方法http://www.cse.psu.edu/~furer/Papers/mult.pdf 做到了 $O(n \log n * 2^{\log^{**} n})$
似乎是至今时间复杂度最低的吧...

[ 本帖最后由 Mgccl 于 2008-6-27 12:42 编辑 ]

gxqcn · 发表于 2008-6-27 12:38:32

原帖由 Mgccl 于 2008-6-27 12:11 发表
很奇特...latex不能弄出*出来...

可以的，连用两个即可：** 表示 $**$；xx 表示 $xx$
参见：http://bbs.emath.ac.cn/viewthrea ... p;fromuid=8#pid1283 中的表格。

gxqcn · 发表于 2008-6-27 12:48:40

请教：$ \log ** n $ 是什么意思？

mult.pdf (268 KB, 下载次数: 9)

无心人 · 发表于 2008-6-27 13:08:21

楼主说的论文的方法似乎只能在小n 上有效吧

mathe · 发表于 2008-6-27 13:14:01

原帖由 gxqcn 于 2008-6-27 12:48 发表
请教：$ \log ** n $ 是什么意思？

好像论文里面对于$log^{**}n$根本没有定义过

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

呵呵

即使等于$logn$ 也不可能比公认的算法快
n达到一定值，二次对数项总远小于指数项吧
$loglog n < 2^{logn}$

在某种意义上 $2^{logn} = cn$

[ 本帖最后由无心人于 2008-6-27 13:18 编辑 ]

无心人 · 发表于 2008-6-27 13:21:06

找到了
那个*是个注释标志
下面有解释
1 lg refers to the logarithm to the base 2

呵呵，这个论文是否民间专家写的？？？？

mathe · 发表于 2008-6-27 13:22:50

不应该是那个注释，应该后面很多地方都用到带*的log.
不过我也有些怀疑，毕竟文章里面使用了一个不通用符号又不解释其意义是有点不正常。

gxqcn · 发表于 2008-6-27 13:33:18

原帖由 无心人 于 2008-6-27 13:21 发表
找到了
那个*是个注释标志
下面有解释
1 lg refers to the logarithm to the base 2

那个是针对正文第7行里的 $O(n^{lg3})$ 的注释。

shshsh_0510 · 发表于 2008-6-27 13:36:11

我想可能是 lglglg...lgn 的意思

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

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

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。