Python 复杂性引用？

Question

是否有任何 Python 复杂性引用？在 cppreference ，例如，对于许多函数(例如 std::array::size 或 std::array::fill )，有一个 complexity 部分描述了它们的运行复杂性，与容器大小成线性关系 em> 或 常量。

我希望 python 网站上出现相同的信息，也许，至少对于 CPython 实现。例如，在 list reference , 在 list.insert 我希望看到 complexity: linear;我知道这个案例(以及许多其他与容器相关的操作)涵盖了here ，但许多其他情况并非如此。以下是几个例子:

• tuple.__le__ 的复杂度是多少？似乎在比较两个大小为 n、k 的元组时，复杂度约为 O(min(n,k))(然而，对于小的 n，它看起来不同)。
• random.shuffle 的复杂度是多少？ ?它似乎是 O(n)。似乎 random.randint 的复杂性是 O(1)。
• 字符串的__format__方法的复杂度是多少？它在输入字符串的大小上似乎是线性的；但是，当相关参数的数量增加时，它也会增加(比较 ("{0}"*100000).format(*(("abc",)*100000)) 与 ("{}"*100000).format(*(("abc",)*100000))).

我知道 (a) 这些问题中的每一个都可以自己回答，(b) 可以查看这些模块的代码(即使有些是用 C 编写的)，以及 (c) StackExchange 不是用于用户请求的 python 邮件列表。所以:这不是文档功能请求，只是两个部分的问题:

1. 你知道这样的资源是否存在吗？
2. 如果没有，你知道在什么地方可以要求这样，或者你能建议我为什么不需要这样吗？

Answer 1

CPython 的算法非常出色，而且操作的时间复杂度通常只是您对一个好的标准库所期望的最佳值。

例如:

元组排序必须是O(min(n,m))，因为它通过逐元素比较来工作。

random.shuffle 是 O(n)，因为这是现代 Fisher-Yates shuffle 的复杂性。

.format 我 imagine 是线性的，因为它只需要一次扫描模板字符串。至于你看到的区别，CPython 可能足够聪明，可以缓存两次使用的相同格式代码。

文档确实提到了时间复杂度，但通常只有在它不是您所期望的时候——例如，因为 deque 是用双向链表实现的，它是 explicitly mentioned因为在中间有 O(n) 用于索引。

文档是否会因在适当的地方调用时间复杂度而受益？我不确定。文档通常按照它们应该用于的内容来呈现内置函数，并针对这些用例进行了优化。强调时间复杂性似乎要么是无用的噪音，要么会鼓励开发人员对 Python 实现本身进行二次猜测。