Python3 默认数据结构（列表、字典、元组...等）的计算复杂度是多少？
（内存复杂性问题也很有趣。）
我发现了什么：http ://wiki.python.org/moin/TimeComplexity - 恐怕是关于 python 2，不是吗？
问问题
344 次
2 回答
2
wiki 条目适用于 Python 2 和 3 的 CPython。这些类没有更改。其他实现可能会有所不同，但如果他们希望人们将代码从 CPython 移植到 xpython，则它们必须相似。例如，使用链表作为列表类型的 Python 需要相当不同的编程风格和代码重新排列才能正常工作；-)。
在 3.3 中，dict 类发生了变化，使得一个类的多个实例的_dict_s 共有的一些信息是共享的，而不是重复的。这主要影响具有 100 或 1000 个某个类实例的人，并将节省大约 1/3 的 dict 空间（我认为），这是一个不会改变空间复杂度类的常数因素。
更重要的是，(unicode) str 类已被完全重写，只使用所需的字节/字符。结果通常会减少空间和时间，但主要影响应该是 O(xxx) 符号忽略的乘数。
于 2012-05-28T23:00:01.750 回答
1
计算复杂度与求解方式有关。独立地，如果 Python 3 更快与否，复杂性将是相同的——除非问题没有使用原则上不同的算法来解决。
有时，具有相同名称的抽象数据结构可能会有所不同（例如 Python 2 字符串与 Python 3 字符串，或 int，Python 2 中的 long 与 Python 3 中的广义 int）。
我没有检查它，但我的猜测是 Python 2 和 Python 3 在这个意义上没有区别。
于 2012-05-24T07:48:00.417 回答