algorithm - Strassen 的 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)。