Strassen的n位数乘法算法(2路分割与3路分割)

Question

Strassen的整数乘法算法有一个版本，它使用三向拆分(将n位数字分成n/3位的3部分)，所需时间为O(n^1.46)。

我的问题是，为什么这种方法通常不是使用O(n^1.59)的通常的双向拆分的首选方法？有什么想法或链接可以帮助我理解吗？(我在网上查了一下，但什么也找不到)

Answer 1

这是因为在实践中，第二种方法会慢一些。O符号并不总是与实际的运行速度相对应。

示例：

f(n) = 1000*n
g(n) = n*lg(n)

O( f(n) )比O(g(n))更好，使得f(n)“更快”，而在实践中，n永远不会大到让我们更喜欢f(N)。