是否有程序化操作Big

是否有程序化操作Big-O复杂性的库？(Is there a library for programmatic manipulation of Big-O complexities?)

我对可以推断自己时间复杂性的编程语言感兴趣。 为此，以某种方式以编程方式表示时间复杂度将非常有用，这将允许我执行以下操作：

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，但我并没有特别依赖语言。 我已尝试过同情 ，但我无法在那里找到我需要的东西。

是否有提供此功能的库？ 如果没有，是否有一种简单的方法可以使用符号数学库来完成上述操作？

编辑 ：我按照@ Patrick87的建议编写了一个简单的库 ，它似乎有效。 不过，如果有其他解决方案，我仍然感兴趣。

I'm interested in programming languages that can reason about their own time complexity. To this end, it would be quite useful to have some way of representing time complexity programmatically, which would allow me to do things like:

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)

I'm using Python at the moment, but I'm not particularly tied to a language. I've experimented with sympy, but I haven't been able to find what I need out of the box there.

Is there a library that provides this capability? If not, is there a simple way to do the above with a symbolic math library?

EDIT: I wrote a simple library following @Patrick87's advice and it seems to work. I'm still interested if there are other solutions for this problem, though.

最满意答案

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

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

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

编辑2：我建议不要尝试从头开始构建这个，而不使用计算机代数系统。 你最终将不得不编写自己的计算机代数系统，这是一项很多工作，如果你想做正确而且不要太慢，那就更需要工作。 已经存在大量已经存在的系统，其中包括许多可以作为代码构建库的库（例如SymPy）。

SymPy currently only supports the expansion at 0 (you can simulate other finite points by performing a shift). It doesn't support the expansion at infinity, which is what is used in algorithmic analysis.

But it would be a good base package for it, and if you implement it, we would gladly accept a patch (nb: I am a SymPy core developer).

Be aware that in general the problem is tricky, especially if you have two variables, or even symbolic constants. It's also tricky if you want to support oscilitory functions. EDIT: If you are interested in oscillating functions, this SymPy mailing list discussion gives some interesting papers.

EDIT 2: And I would recommend against trying to build this yourself from scratch, without the use of a computer algebra system. You will end up having to write your own computer algebra system, which is a lot of work, and even more work if you want to do it right and not have it be slow. There are already tons of systems already existing, including many that can act as libraries for code to be built on top of them (such as SymPy).