时间戳

首页 > 解决方案 > 时间复杂度 - Python eval 的 BigO 表示法

python - 时间复杂度 - Python eval 的 BigO 表示法

问题描述

Python 用于评估数学表达式的 eval 的时间复杂度是多少？我找不到任何说明它的来源。我的假设是 O(n) ，其中 n 是表达式中运算符的数量。

如果有人提到了说明这一点的网站，如果您能分享，将不胜感激。

标签： pythontime-complexitybig-oeval

解决方案

运算符没有时间复杂度。对值进行操作。

例如：

  • 1 + 1的时间复杂度O(1)；两个整数相加很简单(*)
  • [1, 2, 3] + [4, 5, 6]具有不同的时间复杂度，O(len([1, 2, 3]) + len([4, 5, 6])因为连接两个列表需要将两个列表中的所有引用复制到新的列表对象。对于一般情况，list_len_N + list_len_K是一个O(N+K)操作。

您可以在Python wiki中查找对常见 Python 类型的操作的时间复杂度，以及一些额外的常识。例如，每当一个操作必须产生一个新对象时，都要考虑一个副本。+在两个列表上生成一个新的列表对象，因此它涉及复制和扩展操作。

当在不同类型上使用多个运算符时，算法复杂性的正常规则适用；对顺序操作中的复杂操作求和，但O(N) + O(N)仍然是线性O(N)的。

* Python 的整数类型是无限制的，所以时间复杂度稍微复杂一点，因为 CPython 内部的 C 实现可以使用 NC 整数来表示值。在实践中，这不是问题，因为与为动态语言运行解释器循环相比，添加小整数和大整数之间的差异变得毫无意义。

推荐阅读