搜索記錄的時間複雜度？

假設在特定時間在德里地鐵有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

回答