搜索记录的时间复杂度？

假设在特定时间在德里地铁有100 000名车手。当我们触摸我们的智能卡退出电台时，我们需要不到一秒的时间来检索我们的记录，并且机器显示剩余的余额。机器如何在不到一秒的时间内搜索到唯一的卡片ID，理论上它应该花费（log n）时间，对于100 000条记录，时间为5秒？搜索记录的时间复杂度？

2016-04-26 hitesh

如果不知道单个操作的速度有多快，则无法将O（）与真实世界进行比较。例如如果您的数据库运行在原始IBM PC 8086-4.77mhz上，单个'n'将花费很长时间。在现代多GB的CPU上运行它。他们基本上执行相同数量的'n'，但现代机器会在很短的时间内完成那些'n'。 –

为什么需要'log n'来搜索可能的索引记录？任何明智的哈希表实现都可以在'O（1）'中进行搜索，并且由于卡ID位于地铁的控制之下，因此没有理由认为哈希是不完美的。即使你的笔记本电脑也可以在一个包含几百万条目的Java HashMap中查找一个值，很容易在第二个... –

你可以使用散列表，因此访问成本是O（1） – HamoriZ

哈希表 - 它将是O（1）。智能卡的唯一ID肯定会存储在哈希表中。如果他们将它存储在List中，则搜索操作应该通过一个循环发生并记录n次，但是Hash表只会在一次调用中检索。

2016-04-27 14:26:57 sbk

回答