这些Dictionary方法的复杂性是什么？
任何人都可以解释下面的Dictionary方法的复杂性是什么？
ContainsKey(key) Add(key,value);
我想弄清楚我写的方法的复杂性：
public void DistinctWords(String s) { Dictionary d = new Dictionary(); String[] splitted = s.split(" "); foreach ( String ss in splitted) { if (!d.containskey(ss)) d.add(ss,null); } }
我假设2个字典方法具有log（n）复杂度，其中n是字典中的键数。 它是否正确？
作为一个整体，这个例程实际上是O（m）时间复杂度，m是搜索中的字符串数。
这是因为Dictionary.Contains和Dictionary.Add都是（通常）O（1）操作。
（它稍微复杂一些，因为Dictionary.Add对于词典中的n个项目可以是O（n），但只有当词典容量很小时才会这样。因此，如果你构建一个具有足够大容量的字典，对于m个字符串条目，它将是O（m）。）
话虽这么说，如果你只是使用Dictionary进行存在检查，你可以使用HashSet 。 这将允许你写：
public void DistinctWords(String s) { HashSet hash = new HashSet (s.Split(' ')); // Use hash here...
由于您的字典是局部变量，并且未存储（至少在您的代码中），您还可以使用LINQ：
var distinctWords = s.Split(' ').Distinct();
它写在Dictionary的文档中…
Dictionarygenerics类提供从一组键到一组值的映射。 字典的每个添加都包含一个值及其关联的键。 通过使用其键来检索值非常快，接近于O（1），因为Dictionary类是作为哈希表实现的。
而对于添加function：
如果Count小于容量，则此方法接近O（1）操作。 如果必须增加容量以容纳新元素，则此方法变为O（n）操作，其中n为Count。
两种方法都有不变的复杂性
- ContainsKey（键） – O（1）
- 添加（键，值） – O（1）
这是不正确的，通常字典/散列表查找是O（1）。 为此，它将从您正在寻找的密钥生成哈希值，并仅将其与具有相同哈希值的项进行比较 – 使用良好的哈希算法，这被认为是O（1）整体（ 摊销的 O（1） – 仅在罕见的情况，必须增加容量，你有O（n））。
两者都是恒定的时间：
http://msdn.microsoft.com/en-us/library/kw5aaea4.aspx
http://msdn.microsoft.com/en-us/library/k7z0zy8k.aspx
但有一点需要注意：
“如果Count小于容量，则此方法接近O（1）操作。如果必须增加容量以容纳新元素，则此方法变为O（n）操作，其中n为Count。”
ContainsKey和Add方法接近O（1）。
ContainsKey文档：
该方法接近O（1）操作。
添加文档：
如果Count小于容量，则此方法接近O（1）操作。 如果必须增加容量以容纳新元素，则此方法变为O（n）操作，其中n为Count。
如果您使用的是Framework 3.5或更高版本，则可以使用HashSet而不是具有虚拟值的字典：
public void DistinctWords(String s) { HashSet d = new HashSet