这些Dictionary方法的复杂性是什么？

Question

任何人都可以解释以下Dictionary方法的复杂性是什么？

ContainsKey(key)
Add(key,value);

我想弄清楚我写的方法的复杂性:

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);
    } 
}

我假设2个字典方法具有log(n)复杂度,其中n是字典中的键数.它是否正确？

Answer 1

它写在Dictionary的文档中......

Dictionary泛型类提供从一组键到一组值的映射.字典的每个添加都包含一个值及其关联的键.通过使用其键来检索值非常快,接近于O(1),因为Dictionary类是作为哈希表实现的.

对于添加功能:

如果Count小于容量,则此方法接近O(1)操作.如果必须增加容量以容纳新元素,则此方法变为O(n)操作,其中n为Count.

Answer 2

两种方法都有不变的复杂性

• ContainsKey(键) - O(1)
• 添加(键,值) - O(1)

Answer 3

总的来说,这个例程实际上是O(m)时间复杂度,m是搜索中的字符串数.

这是因为Dictionary.Contains和Dictionary.Add都是(通常)O(1)操作.

(它稍微复杂一些,因为Dictionary.Add对于词典中的n个项目可以是O(n),但只有在词典容量很小的情况下才会这样.因此,如果你在前面构造一个具有足够大容量的词典,对于m个字符串条目,它将是O(m).)

话虽这么说,如果你只使用字典进行存在检查,你可以使用HashSet<string>.这将允许你写:

  public void DistinctWords(String s)
  {
     HashSet<string> hash = new HashSet<string>(s.Split(' '));

     // Use hash here...

由于您的字典是局部变量,并且未存储(至少在您的代码中),您还可以使用LINQ:

 var distinctWords = s.Split(' ').Distinct();

Answer 4

这是不正确的,通常字典/散列表查找是O(1).为此,它将从您正在寻找的密钥生成哈希值,并仅将其与具有相同哈希值的项进行比较 - 使用良好的哈希算法,这被认为是O(1)整体(摊销的 O(1) - 仅在罕见的情况,必须增加容量,你有O(n)).