10
我在解決this LeetCode problem時遇到了一個問題。雖然我的解決方案已被系統接受，但在線搜索下列問題後，我仍然沒有任何想法： What is the time complexity of dict.keys() operation?它是否返回密鑰視圖或實際列表（存儲在內存中）密鑰？Python中dict.keys（）的時間複雜度是多少？
A
回答
5
在Python 2中，它是O（n），它構建了一個新列表。在Python 3中，它是O（1），但它不返回一個列表。要從字典的keys中繪製隨機元素，您需要將其轉換爲列表。
這聽起來像你可能使用random.choice(d.keys())爲該問題的第3部分。如果是這樣，那就是O（n），你錯了。您需要實現自己的哈希表或者維護單獨的元素列表，而不會犧牲平均情況下的O（1）插入和刪除操作。
+0
我用'返回self.elements.keys（）[randint（0，len（self.elements） - 1）]'它被接受了（'self.elements是一個dict對象'）。 – Jason
+0
@Jason：是的，那不是O（1）。 – user2357112
+0
正如你所說的「在Python 3中，它是O（1）」。如果'self.elements.keys（）'是'O（1）'，那麼整個表達式將在'O（1）'中運行。如果我犯了錯誤，請糾正我:) – Jason
相關問題
- 1. Collection.toArray（）的時間複雜度是多少？
- 2. Python中collections.Counter（）的時間複雜度是多少？
- 3. Python中zip（）的時間複雜度是多少？
- 4. 減少時間複雜度
- 5. 我的代碼中的時間複雜度是多少
- 6. Java中TreeSet的lower（）/ higher（）的時間複雜度是多少？
- 7. 方案中'assoc'函數的時間複雜度是多少？
- 8. Ruby中Array＃uniq方法的時間複雜度是多少？
- 9. TreeSet中有序操作的時間複雜度是多少？
- 10. Java中LinkedList.getLast（）的時間複雜度是多少？
- 11. clojure中count函數的時間複雜度是多少？
- 12. C++中std :: next_permutation（）函數的時間複雜度是多少？
- 13. java中lastIndexOf的時間複雜度是多少？
- 14. java中StringBuilder.append（）的時間複雜度是多少？
- 15. java中HashMap.containsValue（）的時間複雜度是多少？
- 16. 鏈式散列表中的時間複雜度是多少
- 17. 分時排序算法的時間複雜度是多少？
- 18. 從Python中列表彈出元素的時間複雜度是多少？
- 19. 下面的遞歸函數的時間複雜度是多少
- 20. NavigableMap的floorEntry（）方法的時間複雜度是多少？
- 21. 下面的僞代碼的時間複雜度是多少？
- 22. AngularJS的髒檢查算法的時間複雜度是多少？
- 23. 我的代碼的時間複雜度是多少？
- 24. 樹遍歷的時間複雜度是多少？
- 25. 以下代碼的時間複雜度是多少？
- 26. 爬山算法的時間複雜度是多少？
- 27. 代碼的時間複雜度是多少？
- 28. 以下循環的時間複雜度是多少
- 29. unordered_set <int> :: iterator it + n的時間複雜度是多少？
- 30. 這個函數的時間複雜度是多少？
在Python 3.x中，它的複雜性是'0（1）'。在Python 2.x中，它返回一個列表，以便填充它或在其上執行一些查找需要'0（n）'。 – ozgur
你問關於Python2還是Python3？ –
@ozgur - True，但是對於{} .keys（）中的_：pass'在任一版本中都是'O（n）'。 –