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

Question

你能否谈谈随着我们进一步“嵌套”字典，其复杂性如何增加？

例如，当我按照以下方式添加一个元素时：

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

我认为查找时间对于任何字典应该是相同的（常数时间O(1)），但如果我像这样添加元素，它会显著改变吗？

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

- Shiv

---

你是否意识到，维度为26的数组将至少容纳2^26=67108864个不同的字典（假设每个维度允许2个不同的值；对于每个维度3个值，则有2541865828329个字典，这远远超出了PC的处理能力）？ - user1196549

你似乎没有理解“O(1)”的概念。如果你执行一个“O(1)”操作固定次数，你仍然得到“O(1)”。 - skyking

这个 Stack Overflow 的回答解释了为什么常数元素并不重要（除了它确实很重要）。 - David Mašek

@YvesDaoust 感谢您澄清这一点..我很好奇嵌套字典对时间和内存会产生什么影响 :) - Shiv

Answer 1

Python的字典实现不会随嵌套而改变，因此查找所需的算法复杂度不会改变。就Python而言，每个 [key] 订阅与对象来自何处无关。

每次查找仍然是O(1)。查找嵌套元素是深度次O(1)查找。由于您通过使用文字符号硬编码深度，所以您所拥有的仍然是O(1)，因为常数乘子不影响大O复杂度。

- Martijn Pieters

Answer 2

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

这基本上与以下内容相同

temp_a = dict_name[a]
temp_b = temp_a[b]
temp_c = temp_b[c]
temp_c[d] = 0

所以，您只需要进行三次查找，从字典中获取一个对象，该对象恰好是另一个字典。然后，在最后一步中，进行一个字典分配。

正如我们所知道的，字典查找平均需要常数时间，因此所有这四个操作本身都是O(1)。组合起来，您可以得到4×O(1)，仍然是O(1)(因为对于大O而言，常数因子并不重要)。

如果现在增加嵌套的深度，您将会得到更多的temp_y = temp_x[k]行，这还是常数时间。因此，您只会在k × O(1)中增加因子k。正如之前所说，只要k是常数，因子对于大O并不重要，因此无论嵌套深度如何，您都将保持常数时间。

- poke