Python 3中dict.keys()对象转换为集合的时间复杂度是多少？

Great question—this is a common point of confusion when working with dictionary views vs. lists, so let's break it down clearly.

First, let's recap what you already know:

• dict.keys() returns a dict_keys object, which is a view of the dictionary's keys. Creating this view is indeed O(1) time because it doesn't copy any data—it just references the dictionary's underlying hash table directly.
• Converting a list to a set (set(some_list)) is O(n) because you have to iterate over every element, compute its hash, and insert it into the set.

Now, for your main question: What's the time complexity of set(some_dict_keys_obj)?

The short answer is O(n), where n is the number of keys in the dictionary. Here's why:

• Even though dict_keys is a view that gives you O(1) access to the keys as a group, converting it to a set requires iterating over every single key in the view. Each insertion into the set is average O(1) (since dictionary keys are already hashable and unique—no duplicates to handle!), but you still have to do this for all n keys.
• The practical difference between set(dict_keys) and set(list) is that the dictionary's keys are already pre-hashed (since the dictionary itself relies on hashing for lookups). This means converting dict_keys to a set might run faster than converting a list of the same keys, but the asymptotic time complexity remains O(n) either way.

As a side note: When you run set(some_dict_obj), Python implicitly iterates over the dictionary's keys (just like looping over some_dict does), so this is exactly equivalent to set(some_dict.keys()). Its time complexity is also O(n) for the same reasons above.

To sum up: The O(1) cost of dict.keys() only applies to creating the view object. Any operation that requires collecting all the keys (like converting to a set) will always be linear in the number of keys, because you have to process each one once.

内容的提问来源于stack exchange，提问作者Jorge Massih