BigO用於字典方法'get（key）'

有沒有人知道python字典'get（key）'方法的O（？）？BigO用於字典方法'get（key）'

我已經用cProfile模塊對它進行了測試，並獲得了與字典中100,1000,10000,100000,1000000,100000000條記錄相同的時間結果。

這是否意味着python的字典爲任何密鑰提供O（1）訪問時間？

2013-06-04 pydevd

請參閱http://wiki.python.org/moin/TimeComplexity –

是的。字典被實現爲散列鍵，其具有用於查找的O（1） – karthikr

可能的[訪問Python字典的時間複雜度]的重複（http://stackoverflow.com/questions/1963507/time-complexity-of-accessing-a- python-dict） – jamylak

答案是肯定的，因爲Python字典使用哈希來存儲密鑰。而一個散列表有O(1)訪問其密鑰的平均時間複雜性 - 在這裏閱讀更多http://en.wikipedia.org/wiki/Hash_table。

密鑰檢索的最壞情況是O(n)，其中n是dictionary中的密鑰數。（@Michael Butscher）。

2013-06-04 19:58:40

除了具有大量散列衝突的病例。最壞的情況是O（n），其中n是鍵的數量 –

儘管最壞的情況非常非常非常難以達到。 –

感謝您收到@MichaelButscher！在你提到這件事之前，我並不知道這甚至是可能的，因爲彩虹桌非常成功，人們不會懷疑他們會有瓶頸。 –

是的，它確實是O（1）的任何鍵。

2013-06-04 19:59:41

回答