n 位数的斯特拉森乘法算法(2 路分裂与 3 路分裂)

Question

有一个版本的Strassen整数乘法算法使用三向分割（将n位数分成n/3位的3部分）并取O（n^1.46）。

我的问题是为什么这种方法通常不优于使用 O（n^1.59） 的 2 路拆分的通常方法？有什么想法或链接可以帮助我理解吗？（我在网上查了一下，但找不到任何东西）

Answer 1

那是因为在实践中，第二个会更慢。O 表示法并不总是与实际运行速度相对应。

例：

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

O（f（n）） 比 O（g（n）） 更好），使 f（n） "更快"，而在实践中 n 永远不会大到让我们更喜欢 f（n）。