psi*_*lia 18 algorithm math complexity-theory big-o time-complexity
对于基本算术运算的广泛算法,如乘法,平方根,对数,标量和矩阵乘积,Big-O复杂度是多少？
在Big-O复杂性方面是否存在更高效的外来算法,但在实际解决方案中并不是非常普遍(例如,在流行的软件库中没有实现)？
ken*_*ytm 18
请参见http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations
方矩阵的矩阵乘积:
还有一个O(N 2.38)Coppersmith-Winograd算法,但由于巨大的隐藏常数,我不认为它是广泛传播的.
Big-int乘法:
2008年还发布了一个n log n·2 O(log*n)算法,但这个算法太新了,无法普及.
通常,天真的方法对于正常大小的输入来说足够好.
操作没有复杂性,算法也没有.例如,存在各种平方根算法,它们将具有不同的复杂性.
您将大多数简单操作视为O(1),因为您的输入大小通常是固定的(即32位或64位).
在正常情况下,无论输入的"大小"如何,您的平台将执行与乘法,平方根,对数等完全相同的操作(即int a = 0;并且int b = Int32.MaxValue都是32位整数).
一旦你开始查看矩阵或表示任意精度数字,它就会变得有趣,但有人已经链接了维基百科摘要,所以我不会进入那个.
只是不要使用Schönhage-Strassen来增加"正常"的小数字.它会让我哭泣.仅仅因为算法是O(n 2)并不意味着它是坏的 - 特别是当n几乎总是2 5或2 6时.