[解決済み] アクセス時間O(1)」とはどういう意味ですか？

質問

O(1) access time"という言葉を、quot;速いという意味で使っているのを見たことがありますが、意味がよくわかりません。同じ文脈で目にする他の用語は、"O(n) access time"です。どなたか、これらの用語の意味をわかりやすく説明していただけませんか？

参照

• ビッグ・オー表記とは何ですか？使っていますか？
• 8歳児にBIG-O？

解決方法は？

Order of complexityを読みたくなりますね。

http://en.wikipedia.org/wiki/Big_O_notation

要するに、O(1)とは、セットのデータ量にかかわらず、14ナノ秒とか3分とか、一定の時間がかかるということです。

O(n)とは、セットの大きさに比例して時間がかかるという意味で、2倍の大きさのセットには2倍の時間がかかるということです。 この中に100万個のオブジェクトを入れたくはないでしょう。