在Python 3中調用dict.keys（）的複雜性是什麼？

python中dict.keys()的漸近複雜性是什麼？我發現this website但它沒有答案。我正在使用Python 3，但我想這不是特定於版本的。在Python 3中調用dict.keys（）的複雜性是什麼？

它是'O（1）'，但需要一個額外的函數調用。 –

它的特定版本是用Python 2'keys（）'返回一個列表，在Python 3中它返回一個字典視圖對象。 –

您是否正在查看dict.keys（）中的操作，例如在字典視圖中的生成本身？ –

在Python 3中，dict.keys()返回view object。實質上，這只是一個直接放到字典鍵上的窗口。例如，沒有循環散列表來構建新的對象。這使得它稱爲一個常量，即O（1）操作。

查看字典的對象是從here開始執行;新視圖對象的創建使用dictview_new。這個函數所做的就是創建新的對象，該對象指向字典並增加引用計數（用於垃圾跟蹤）。

在Python 2中，dict.keys()返回一個列表對象。爲了創建這個新列表，Python必須遍歷散列表，將字典的鍵放入列表中。這被實現爲功能dict_keys。這裏的時間複雜度與字典的大小成線性關係，即O（n），因爲必須訪問表中的每個槽。

N.B. Python 2中的dict.viewkeys()與Python 3中的dict.keys()的做法相同。

2015-08-24 13:17:46

回答