我对可以推理自己的时间复杂度的编程语言感兴趣。为此，以编程方式表示时间复杂度的某种方法将非常有用，这将允许我执行以下操作：
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的建议编写了一个简单的库，它似乎有效。不过，如果这个问题还有其他解决方案，我仍然感兴趣。
SymPy 目前仅支持 0 处的扩展（您可以通过执行移位来模拟其他有限点）。它不支持无穷远的扩展，这是算法分析中使用的。
但它将是一个很好的基础包，如果你实现它，我们很乐意接受一个补丁（注意：我是SymPy核心开发人员）。
请注意，一般来说，这个问题很棘手，特别是如果你有两个变量，甚至是符号常量。如果您想支持振荡函数，这也很棘手。编辑：如果你对振荡函数感兴趣，这个SymPy邮件列表讨论提供了一些有趣的论文。
编辑2：我建议不要尝试从头开始构建它，而不使用计算机代数系统。 你最终将不得不编写自己的计算机代数系统，这是很多工作，如果你想把它做好并且不让它变慢，甚至更多的工作。 已经有大量的系统已经存在，包括许多可以充当在其上构建代码的库（例如SymPy）。
实际上，您正在构建/查找一个可以处理以下内容的表达式简化器：
-
+ （在您的术语中：
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)" ），而不是函数。
如果您只使用 big-O 表示法，并且对一个函数的增长速度是比另一个函数增长得更快还是更慢感兴趣，那么渐近地说......
- 给定函数 f 和 g
- 使用计算机代数包计算 n 变为 f（n）/g（n） 的无穷大时的极限
- 如果极限发散到 +无穷大，则 f> g - 在 g = O（f） 的意义上，但 f ！= O（g）。
- 如果极限发散为 0，则 g <f。> 如果极限收敛到有限数，则 f = g（在 f = O（g）
- 和 g = O（f）的意义上）
- 如果限制未定义...打败我！