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

Question

斯特拉森的整数乘法算法的版本使用三路分裂（将n位数除以3位n/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） “更快”，而在实践中Ñ永远不会大足以让我们更喜欢f（n）。