问搜索记录的时间复杂度？
EN

Stack Overflow用户

提问于 2016-04-26 23:49:33

回答 1查看 60关注 0票数 0

假设在给定的时间，德里地铁有10万名乘客。当我们触摸智能卡离开车站时，只需不到一秒钟的时间就可以检索我们的记录，机器就会显示我们的余额。机器如何在不到一秒的时间内搜索唯一的卡id，而从理论上讲，100000条记录应该花费(log )5秒的时间？

发布于 2016-04-27 22:26:57

哈希表-它应该是O(1)。智能卡的唯一in肯定会存储在哈希表中。如果他们将其存储在列表中，搜索操作应该通过循环发生，并花费log n时间，但哈希表将在一次调用中检索。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/36869865

复制

相似问题

问搜索记录的时间复杂度？EN