在Javascript中按值查找键的时间复杂性



我知道按键查找哈希值是O(1)(恒定时间(,但如果您找到了具有特定值的键,这是一样的吗?我正在使用查找密钥

const answer = Object.keys(dict).find(key => dict[key] === 1);

dict是一个具有整数键的对象。

这是O(n)的时间复杂性,因为您正在对数组(Object.keys返回的数组(执行线性搜索。最坏的情况是,您想要的项将是数组中的最后一个项(或者它根本不在数组中(,这将需要n操作来确定(n是数组的长度(,因此,这是O(n)时间。

最新更新