为什么dict在这么多操作中都具有最差情况O(n)?
dict如何实现线性的线性时间查找冲突?我假设它被实现为由列表支持的哈希表。我以为更好的实现是对各种操作使用O(log(n)),而是使用树来支持表。幕后是否发生了一些不可思议的事情,以保持恒定时间的查找尽可能长的生命?
顺便说一下,我的来源是:
http://www.google.com/search?sourceid=chrome&ie=UTF-8&q=python+complexity
-
除接触所有元素的操作(例如迭代和复制)(在这种情况下,显然是O(n))之外,大多数操作的Dict为O(1)。
请参阅:http:
//wiki.python.org/moin/TimeComplexity它具有O(n)最坏的情况,因为您总是可以构造一个病理示例,其中所有键都具有相同的哈希值。