新未名空间

现在最快的是O(nlogn)，这就已经比任意的O(n^a), a > 1快了

可不可以证明或者证伪无法做到O(n)

（ヅ） 写了： 2023年 12月 16日 16:58 现在最快的是O(nlogn)，这就已经比任意的O(n^a), a > 1快了

可不可以证明或者证伪无法做到O(n)

秦九韶方法就是O(n)啊。

（ヅ） 写了： 2023年 12月 16日 16:58 现在最快的是O(nlogn)，这就已经比任意的O(n^a), a > 1快了

可不可以证明或者证伪无法做到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.

如果我没记错，秦九韶方法是对一个多项式的。

gmo 写了： 2023年 12月 17日 04:41 秦九韶方法就是O(n)啊。

貌似无人证明或证伪。

（ヅ） 写了： 2023年 12月 16日 16:58 现在最快的是O(nlogn)，这就已经比任意的O(n^a), a > 1快了

可不可以证明或者证伪无法做到O(n)

TheMatrix 写了： 2023年 12月 17日 08:55 我记得前段时间出了一个整数乘法的最新算法是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.

让x = 10就是整数了，hoho

gmo 写了： 2023年 12月 17日 04:41 秦九韶方法就是O(n)啊。

这好像不是一回事

我感觉：
不可以
在计算上要完全覆盖各项，本质上就要用某种类似“进制”的方式处理
n lg n应该是最有效的（根据情况，基可以选非2）

用些具体的不很特殊的大n例子应该就可以说明？
比如只是计算13^n, where n=11!+1

应该没有人证明或者否证。这属于FP问题。

乘法算法复杂性没有定论。

通俗来说，

其实就是问：在最坏的情况下，有没有O(n)的算法？

极其可能的是：
在最好的情况下，都没有O(n）。
p(n)*q(n)即使考虑特殊情况(=)r(n)甚至只是(对任意大的n)x^n,都没有O(n)算法。


在实际应用中，很可能完全找不到某种实用的n*log(...log(n))算法，即使那种算法在理论上被发现是存在的。

因此，n *log(n)极可能就是(实际可行的）最佳算法。