レコードを検索するための時間複雑度？

与えられた時間にデリー首都圏に100,000人のライダーがいるとします。私たちがスマートカードに触れて駅を出るとき、私たちの記録を取り出すのに少し時間がかかり、マシンは残っている残高を表示します。どのようにしてマシンは一秒以内に一意のカードIDを検索できますか？理論的には100 000レコードで5秒かかる（ログn）時間が必要です。レコードを検索するための時間複雑度？

出典

2016-04-26 hitesh

O（）と実世界を比較することはできません。例えばあなたのDBがオリジナルのIBM PC、8086-4.77mhzで動作している場合、単一の 'n'は長い時間がかかります。現代のマルチghzのCPU上でそれを実行します。両方とも本質的に同じ数の「n」を実行するが、現代のマシンはそれらの「n」をより少ない時間で行うだろう。 –

「log n」を検索するのはなぜでしょうか、おそらくインデックスされたレコードですか？分かりやすいハッシュテーブル実装は 'O（1）'で検索でき、カードIDはメトロの管理下にあるので、ハッシュが不完全であると仮定する理由はありません。あなたのラップトップでも、Java HashMapで数百万のエントリを簡単に2番目の値で検索することができます... –

アクセスコストがO（1）であるため、ハッシュテーブルを使用できます。 – HamoriZ

ハッシュテーブル - O（1）になります。スマートカードの一意のIDは、必ずハッシュテーブルに格納されます。彼らがリストに格納する場合、検索操作はループを通して実行され、ログをn回取るべきですが、ハッシュテーブルは1回の呼び出しで検索します。

出典

2016-04-27 14:26:57 sbk

レコードを検索するための時間複雑度？

答えて

関連する問題