python Dictionary.values()的时间复杂度是多少

Question

我已经参考了这个页面，但它显示了Dict.keys((的时间复杂性。https://wiki.python.org/moin/TimeComplexity

此表也显示相同https://www.geeksforgeeks.org/complexity-cheat-sheet-for-python-operations/

字典中查找的时间复杂性。values((列出与集合在这种情况下，它搜索每个键的list，所以对我没有帮助。因为在我的情况下，Dict的所有值都是一个整数。

Q(1(：对于Dict.values((，是O(1(还是O(n(？

Dict = {1:10,2:20,3:30,4:40}
if 10 in Dict.values():
print("YES")

Q(2(：在python中，是否可以通过提供值来获取密钥？[如果提供的值在Dict.values((中多次出现，我想获得所有对应的密钥]

Dict = {1:10,2:20,3:30,4:40}
value = 20

我想通过这个值找到键=2。O(1(有可能吗？因为在O(n(中，我必须检查所有键的值！！！

Answer 1

Q(1(：

我认为它是O(1(

编辑：我错了。这是O(n(。感谢@Roy Cohen和@kaya3。

测试代码：

import timeit
def timeis(func):
def wrap(*args, **kwargs):
start =  timeit.default_timer()
result = func(*args, **kwargs)
end =  timeit.default_timer()
print(func.__name__, end-start)
return result
return wrap
import random
@timeis
def dict_values_test(dic,value):
return value in dic.values()
tiny_dic = {i : 10*i for i in range(1000)}
value = random.randint(1,1000)
dict_values_test(tiny_dic,value)
small_dic = {i : 10*i for i in range(1000000)}
value = random.randint(1,1000000)
dict_values_test(small_dic,value)
big_dic = {i : 10*i for i in range(100000000)}
value = random.randint(1,100000000)
dict_values_test(big_dic,value)

结果：

dict_values_test 2.580000000002025e-05
dict_values_test 0.015847600000000073
dict_values_test 1.4836825999999999

Q(2(：

代码：

def find_key_by_value(dic,find_value):
return [k for k,v in dic.items() if v == find_value]

dic = {1:10,2:20,3:30,4:40,5:40}
print(find_key_by_value(dic,40))

结果：

[4, 5]