是否有一个用于以编程方式操作 Big-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

SymPy 目前仅支持 0 处的扩展（您可以通过执行移位来模拟其他有限点）。它不支持无穷远扩展，这是算法分析中使用的。

但这将是一个很好的基础包，如果你实现它，我们很乐意接受补丁（注意：我是 SymPy 核心开发人员）。

请注意，一般来说，问题很棘手，特别是如果您有两个变量，甚至是符号常量。如果你想支持振荡函数，这也很棘手。编辑：如果您对振荡函数感兴趣，这个SymPy 邮件列表讨论提供了一些有趣的论文。

编辑2：我建议不要在不使用计算机代数系统的情况下尝试从头开始自己构建这个。您最终将不得不编写自己的计算机代数系统，这是一项繁重的工作，如果您想做得正确并且不想让它变慢，则需要更多的工作。已经有大量的系统存在，包括许多可以充当在其之上构建代码的库（例如 SymPy）。