gpt4 book ai didi

sorting - 哈希DoS : how can worst case complexity of Hashtable be O(n^2)?

转载 作者:行者123 更新时间:2023-12-02 16:09:27 24 4
gpt4 key购买 nike

现在你们很多人一定听说过 HashDoS 。发现这一点的研究人员在 their video 中声称Hastable 最坏情况的复杂度是 O(n^2)。怎么会这样?

最佳答案

问题的措辞不正确。研究人员并没有声称“哈希表的最坏情况复杂度是 O(n^2)”。

What they claim是“将 n 个元素插入表中的 [...] 复杂度为 O(n^2)。”所以,单个操作的复杂度是O(n)。这是有道理的:如果所有键都有相同的哈希,那么它们都会进入同一个桶,这只是一个数组或链表,因此需要线性搜索。

关于sorting - 哈希DoS : how can worst case complexity of Hashtable be O(n^2)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8677282/

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