检查字典是否包含某个键的时间复杂度是多少？

Question

4

根据https://wiki.python.org/moin/TimeComplexity，对于给定的字典D，操作D[k]是恒定的。
那么k in D的复杂度是多少？这仍然是恒定的吗？

- Donbeo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Martijn Pieters · Accepted Answer

会员测试与检索项的成本完全相同，因此为O(1)。

这是很合理的，因为为了返回给定键的值，您首先需要确定它是否在字典中。如果检索关键字需要恒定的时间，则首先确定它是否在字典中也只能花费恒定的时间。