python - 嵌套字典的查找时间如何增加？

Question

有人可以评论一下字典的复杂性是如何随着我们进一步“嵌套”它们而增加的吗？

例如我添加一个元素如下:

dict_name[a][b][c][d] = 0

我认为任何字典的查找时间都应该相同(常数时间 O(1))，但如果我添加这样的元素，它会发生显着变化吗？

dict_name[a][b][c]....[z]

Answer 1

Python 的字典实现不会随着嵌套而改变，不，所以查找的算法复杂度不会改变。就 Python 而言，每个 [key] 订阅都独立于您订阅的对象的来源。

每次查找仍然是 O(1)。查找嵌套元素是 深度 时间复杂度为 O(1) 的查找。由于您对深度进行了硬编码(通过使用文字表示法)，您所拥有的仍然是 O(1)，因为常数乘数不会影响 Big-O 复杂性。