时间复杂度最低的整数相乘
有参考价值的算法资料专门发一个帖子,记录时间复杂度最低的整数相乘...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 编辑 ] 原帖由 Mgccl 于 2008-6-27 12:11 发表 http://bbs.emath.ac.cn/images/common/back.gif
很奇特...latex不能弄出*出来...
可以的，连用两个即可：** 表示 $**$；xx 表示 $xx$
参见：http://bbs.emath.ac.cn/viewthread.php?tid=212&page=1&fromuid=8#pid1283 中的表格。 请教：$ \log ** n $ 是什么意思？
:)
楼主说的论文的方法似乎只能在小n 上有效吧 原帖由 gxqcn 于 2008-6-27 12:48 发表 http://bbs.emath.ac.cn/images/common/back.gif
请教：$ \log ** n $ 是什么意思？
好像论文里面对于$log^{**}n$根本没有定义过 呵呵
即使等于$logn$ 也不可能比公认的算法快
n达到一定值，二次对数项总远小于指数项吧
$loglog n <2^{logn}$
在某种意义上 $2^{logn} = cn$
[ 本帖最后由 无心人 于 2008-6-27 13:18 编辑 ] 找到了
那个*是个注释标志
下面有解释
1 lg refers to the logarithm to the base 2
呵呵，这个论文是否民间专家写的？？？？ 不应该是那个注释，应该后面很多地方都用到带*的log.
不过我也有些怀疑，毕竟文章里面使用了一个不通用符号又不解释其意义是有点不正常。 原帖由 无心人 于 2008-6-27 13:21 发表 http://bbs.emath.ac.cn/images/common/back.gif
找到了
那个*是个注释标志
下面有解释
1 lg refers to the logarithm to the base 2
那个是针对正文第7行里的 $O(n^{lg3})$ 的注释。 我想可能是lglglg...lgn 的意思