Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
307 views
in Technique[技术] by (71.8m points)

c# - What is the complexity of these Dictionary methods?

Can anyone explain what is the complexity of the following Dictionary methods?

ContainsKey(key)
Add(key,value);

I'm trying to figure out the complexity of a method I wrote:

public void DistinctWords(String s)
{
    Dictionary<string,string> d = new Dictionary<string,string>();
    String[] splitted = s.split(" ");
    foreach ( String ss in splitted)
    { 
        if (!d.containskey(ss))
            d.add(ss,null);
    } 
}

I assumed that the 2 dictionary methods are of log(n) complexity where n is the number of keys in the dictionary. Is this correct?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

It's written in the documentation for Dictionary...

The Dictionary generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table.

And for the Add function:

If Count is less than the capacity, this method approaches an O(1) operation. If the capacity must be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...