たとえば、.NET Framework 4.5Dictionary<TKey, TValue>クラスのドキュメントを考えてみましょう。
メソッドの備考で、彼らは次のように述べています.ContainsKey
この方法は O(1) 操作に近づきます。
そして、プロパティの備考で、彼らは次のように述べています.Count
このプロパティの値を取得することは、O(1) 操作です。
、、または Big O 記法が一般的に何であるかの詳細を必ずしも求めているわけではないことに注意してください。この「アプローチ」の違いが興味深いと思いました。C#.NETDictionary
違いはありますか？もしそうなら、それは潜在的にどれほど重要ですか？私はそれに注意を払うべきですか？
It's because Dictionary is an implementation of hash tables - this means that a key lookup is done by using a hashing function that tells you which bucket among many buckets contained in the data structure contains the value you're looking up. Usually, for a good hashing function, assuming a large enough set of buckets, each bucket only contains a single element - in which case the complexity is indeed O(1) - unfortunately, this is not always true - the hashing function may have clashes, in which case a bucket may contain more than one entry and so the algorithm has to iterate through the bucket until it finds the entry you're looking for - so it's no longer O(1) for these (hopefully) rare cases.
何かが O(1) であるか、そうでないかのどちらかです。彼らが言おうとしているのは、多数の操作の場合、実行時間は操作ごとに約 O(1) であるということだと思います。
O(1) は一定の実行時間であり、O(1) に近づくと一定に近くなりますが、完全ではありませんが、ほとんどの場合、無視できるほどの増加です。あなたはそれに注意を払うべきではありません。