gpt4 book ai didi

c++ - 链式哈希表的时间复杂度是多少

转载 作者:行者123 更新时间:2023-12-03 07:18:09 28 4
gpt4 key购买 nike

我有一个哈希表,其中包含1000个元素和100个存储桶,每个存储桶最多100个条目。假设一个存储桶有100个条目(即该存储桶列表中的100个项目)。如果我要查找的项目在存储桶列表中排名第100,那么按照big-O表示法的时间复杂度将是多少。 O(100)还是O(n)?还是其他?

最佳答案

big-O表示法的要点是,您不要“假设一个存储桶有100个条目”,而是让其条目数为n,并使用n获得表达式。

对于列表中的n条目,时间复杂度将为O(n),而忽略您使用的任何哈希函数。

请注意,这是最坏的情况(最后一项),平均而言,搜索以O(1)运行。

关于c++ - 链式哈希表的时间复杂度是多少,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24242242/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com