多项式乘法有可能做到O(n)吗?
版主: verdelite, Tlexander
-
- 著名点评
- 帖子: 5295
- 注册时间: 8月 21, 2022, 2:20 pm
-
- 论坛点评
- 帖子: 3268
- 注册时间: 7月 24, 2022, 1:22 pm
-
- 论坛支柱
TheMatrix 的博客 - 帖子: 9751
- 注册时间: 7月 26, 2022, 12:35 am
#3 Re: 多项式乘法有可能做到O(n)吗?
我记得前段时间出了一个整数乘法的最新算法是O(nlogn),多项式乘法应该也是这样吧:
The current fastest algorithm for integer multiplication is the Harvey-Hoeven algorithm, which was developed in 2019. It has a complexity of O(n log n), which means it can multiply two n-digit numbers in roughly n log n steps. However, this algorithm is very complicated and only works for extremely large numbers.
-
- 著名点评
- 帖子: 3274
- 注册时间: 7月 26, 2022, 4:46 pm
- 昵称(选填): 令狐
-
- 著名点评
- 帖子: 3274
- 注册时间: 7月 26, 2022, 4:46 pm
- 昵称(选填): 令狐
-
- 著名点评
- 帖子: 5295
- 注册时间: 8月 21, 2022, 2:20 pm
#6 Re: 多项式乘法有可能做到O(n)吗?
让x = 10就是整数了,hohoTheMatrix 写了: ↑12月 17, 2023, 8:55 am 我记得前段时间出了一个整数乘法的最新算法是O(nlogn),多项式乘法应该也是这样吧:
The current fastest algorithm for integer multiplication is the Harvey-Hoeven algorithm, which was developed in 2019. It has a complexity of O(n log n), which means it can multiply two n-digit numbers in roughly n log n steps. However, this algorithm is very complicated and only works for extremely large numbers.
-
- 著名点评
- 帖子: 5295
- 注册时间: 8月 21, 2022, 2:20 pm
-
- 论坛元老
- 帖子: 15951
- 注册时间: 7月 22, 2022, 3:16 pm
- 来自: 宇宙
- 昵称(选填): 没有马甲
#8 Re: 多项式乘法有可能做到O(n)吗?
我感觉:
不可以
在计算上要完全覆盖各项,本质上就要用某种类似“进制”的方式处理
n lg n应该是最有效的(根据情况,基可以选非2)
用些具体的不很特殊的大n例子应该就可以说明?
比如只是计算13^n, where n=11!+1
不可以
在计算上要完全覆盖各项,本质上就要用某种类似“进制”的方式处理
n lg n应该是最有效的(根据情况,基可以选非2)
用些具体的不很特殊的大n例子应该就可以说明?
比如只是计算13^n, where n=11!+1
-
- 著名写手
- 帖子: 314
- 注册时间: 4月 17, 2023, 8:26 am
#9 Re: 多项式乘法有可能做到O(n)吗?
应该没有人证明或者否证。这属于FP问题。
乘法算法复杂性没有定论。
乘法算法复杂性没有定论。
-
- 论坛元老
- 帖子: 15951
- 注册时间: 7月 22, 2022, 3:16 pm
- 来自: 宇宙
- 昵称(选填): 没有马甲
#10 Re: 多项式乘法有可能做到O(n)吗?
通俗来说,
其实就是问:在最坏的情况下,有没有O(n)的算法?
极其可能的是:
在最好的情况下,都没有O(n)。
p(n)*q(n)即使考虑特殊情况(=)r(n)甚至只是(对任意大的n)x^n,都没有O(n)算法。
在实际应用中,很可能完全找不到某种实用的n*log(...log(n))算法,即使那种算法在理论上被发现是存在的。
其实就是问:在最坏的情况下,有没有O(n)的算法?
极其可能的是:
在最好的情况下,都没有O(n)。
p(n)*q(n)即使考虑特殊情况(=)r(n)甚至只是(对任意大的n)x^n,都没有O(n)算法。
在实际应用中,很可能完全找不到某种实用的n*log(...log(n))算法,即使那种算法在理论上被发现是存在的。
-
- 论坛元老
- 帖子: 15951
- 注册时间: 7月 22, 2022, 3:16 pm
- 来自: 宇宙
- 昵称(选填): 没有马甲
#11 Re: 多项式乘法有可能做到O(n)吗?
因此,n *log(n)极可能就是(实际可行的)最佳算法。