是否有一个程序化操作BigO复杂性的库？

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的建议写了a simple library，它似乎起作用了。不过，我还是对这个问题是否有其他解决方案感兴趣。在

Answer 1

实际上，您正在构建/找到一个表达式简化器，它可以处理：

• +（用您的术语：followed_by）
• *****（用你的话说：inside）
• ^，日志！（表示复杂性）
• 变量（如n，m）
• 常量数（就像2^n中的那样）

例如，当您给出f_time.inside(g_time).followed_by(h_time)时，它可以是如下表达式：

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

，并期望处理器将其输出为：n^3。在

因此，一般来说，您可能希望使用common expression simplifier（如果您希望它有趣，请查看Mathemetica是如何实现的）来获得一个简化的表达式，如n^3+n^(1/2)，然后您需要一个额外的处理器从表达式中选择复杂度最高的术语并去掉其他术语。这很简单，只需使用一个表来定义每种符号的复杂性顺序。在

请注意，在本例中，表达式只是符号，您应该将其写成string（例如：f_time = "O(n)"），而不是函数。在

Answer 2

如果你只使用big-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 3

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

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

请注意，一般来说，这个问题是棘手的，尤其是如果你有两个变量，甚至符号常量。如果您想支持oscility函数，这也很棘手。编辑：如果您对振荡函数感兴趣，thisSymPy邮件列表讨论会给出一些有趣的论文。在

编辑2：我建议不要在没有使用计算机代数系统的情况下，从头开始构建这个系统。你将不得不编写你自己的计算机代数系统，这是一个很大的工作，甚至更多的工作，如果你想做正确的，而不是让它慢。已经有大量的系统已经存在，包括许多可以作为在它们之上构建代码的库（比如SymPy）。在