有没有库可以程序化地操作大O复杂度？

Question

我对那些能自己分析时间复杂度的编程语言很感兴趣。为了实现这个目标，能有一种方法来以编程的方式表示时间复杂度会非常有用，这样我就可以做一些事情，比如：

f_time = O(n)
g_time = O(n^2)
h_time = O(sqrt(n))

fastest_asymptotically = min(f_time, g_time, h_time)  # = h_time
total_time = f_time.inside(g_time).followed_by(h_time)  # = O(n^3)

我现在在用Python，但我并不特别依赖某种语言。我试过使用sympy，但没有找到我需要的功能。

有没有什么库可以提供这种能力？如果没有，是否有简单的方法可以用符号数学库来实现上面的功能？

编辑：我根据@Patrick87的建议写了一个简单的库，看起来是有效的。不过，我还是想知道是否还有其他解决这个问题的方法。

Answer 1

如果你只关注大O符号，并且想知道一个函数的增长速度是比另一个快还是慢，从渐进的角度来看...

1. 假设有两个函数 f 和 g
2. 使用计算机代数软件计算当 n 趋近于无穷大时 f(n)/g(n) 的极限
3. 如果这个极限结果是正无穷大，那么可以说 f 的增长速度比 g 快，也就是 g = O(f)，但 f 不是 O(g)。
4. 如果这个极限结果是 0，那么可以说 g 的增长速度比 f 快。
5. 如果这个极限结果是一个有限的数字，那么可以说 f 和 g 的增长速度是一样的，也就是 f = O(g) 且 g = O(f)。
6. 如果这个极限是未定义的...我也不知道该怎么解释！

Answer 2

其实你正在构建或寻找一个表达式简化器，它可以处理以下内容：

• +（在你的术语中是：followed_by）
• *****（在你的术语中是：inside）
• ^, log, !（用来表示复杂度）
• 变量（比如 n, m）
• 常数（比如在 2^n 中的数字）

举个例子，假设你给出的表达是 f_time.inside(g_time).followed_by(h_time)，它可能表示一个像这样的表达式：

n*(n^2)+(n^(1/2))

你希望这个处理器能把它简化成：n^3。

总的来说，你可能想用一个常见的表达式简化器（如果你想了解得更有趣，可以去看看Mathemetica是怎么做的）来得到一个简化后的表达式，比如 n^3+n^(1/2)。然后你需要一个额外的处理器来选择表达式中复杂度最高的项，并去掉其他的项。这很简单，只需用一个表格来定义每种符号的复杂度顺序。

请注意，在这种情况下，表达式只是符号，你应该把它写成类似 string 的形式（比如你的例子：f_time = "O(n)"），而不是作为函数。

Answer 3

SymPy目前只支持在0点进行展开（你可以通过移动来模拟其他有限点）。它不支持在无穷大处展开，而无穷大展开在算法分析中是很常用的。

不过，SymPy是一个很好的基础包，如果你能实现这个功能，我们会很乐意接受你的贡献（顺便说一下，我是SymPy的核心开发者）。

要注意的是，这个问题一般来说比较复杂，尤其是当你有两个变量，或者甚至是符号常量的时候。如果你想支持振荡函数，那就更麻烦了。补充一下，如果你对振荡函数感兴趣，这个SymPy邮件列表的讨论提供了一些有趣的论文。

补充2：我建议你不要试图从零开始自己构建这个功能，而不使用计算机代数系统。这样你最终会不得不自己写一个计算机代数系统，这工作量非常大，如果想做好而且不让它变得很慢，那就更麻烦了。现在已经有很多现成的系统，包括许多可以作为库供其他代码使用的系统（比如SymPy）。