4

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

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的建议编写了一个简单的库，它似乎有效。不过，我仍然对这个问题是否有其他解决方案感兴趣。

4

3 回答 3

4

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

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

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

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

于 2013-01-25T17:56:15.400 回答
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. 如果限制未定义...击败我！
于 2013-01-24T21:02:02.220 回答
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.

所以一般来说，你可能想要使用一个通用的表达式简化器（如果你想让它变得有趣，去检查Mathemetica是如何做到的）来得到一个简化的表达式n^3+n^(1/2)，然后你需要一个额外的处理器来选择这个术语表达式的最高复杂性并摆脱其他术语。这很容易，只需使用一个表格来定义每种符号的复杂性顺序。

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

于 2013-01-24T21:12:15.507 回答